{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #01 矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: updateMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #01 矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由 <code>0</code> 和 <code>1</code> 组成的矩阵 <code>mat</code>&nbsp;，请输出一个大小相同的矩阵，其中每一个格子是 <code>mat</code> 中对应位置元素到最近的 <code>0</code> 的距离。</p>\n",
    "\n",
    "<p>两个相邻元素间的距离为 <code>1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626667201-NCWmuP-image.png\" style=\"width: 150px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat =<strong> </strong>[[0,0,0],[0,1,0],[0,0,0]]\n",
    "<strong>输出：</strong>[[0,0,0],[0,1,0],[0,0,0]]\n",
    "</pre>\n",
    "\n",
    "<p><b>示例 2：</b></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626667205-xFxIeK-image.png\" style=\"width: 150px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>mat =<b> </b>[[0,0,0],[0,1,0],[1,1,1]]\n",
    "<strong>输出：</strong>[[0,0,0],[0,1,0],[1,2,1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>mat[i][j] is either 0 or 1.</code></li>\n",
    "\t<li><code>mat</code> 中至少有一个 <code>0&nbsp;</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 542&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/01-matrix/\">https://leetcode-cn.com/problems/01-matrix/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [2bCMpM](https://leetcode.cn/problems/2bCMpM/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [2bCMpM](https://leetcode.cn/problems/2bCMpM/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        dist = [[sys.maxsize] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dist[i][j] = 0\n",
    "                else:\n",
    "                    if i-1 >= 0:\n",
    "                        dist[i][j] = min(dist[i][j], dist[i-1][j]+1)\n",
    "                    if j-1 >= 0:\n",
    "                        dist[i][j] = min(dist[i][j], dist[i][j-1]+1)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if mat[i][j] == 0:\n",
    "                    dist[i][j] = 0\n",
    "                else:\n",
    "                    if i+1 < m:\n",
    "                        dist[i][j] = min(dist[i][j], dist[i+1][j]+1)\n",
    "                    if j+1 < n:\n",
    "                        dist[i][j] = min(dist[i][j], dist[i][j+1]+1)\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        \n",
    "        di=[[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        tem=[]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]==0:\n",
    "                    tem.append((i,j))\n",
    "                else:\n",
    "                    matrix[i][j]=-1\n",
    "        step=1\n",
    "        while tem:\n",
    "            l=len(tem)\n",
    "            for i in range(l):\n",
    "                n=tem.pop(0)\n",
    "                for d in di:\n",
    "                    x=n[0]+d[0]\n",
    "                    y=n[1]+d[1]\n",
    "                    if x>=0 and x<len(matrix) and y>=0 and y<len(matrix[0]):\n",
    "                        if matrix[x][y]<0:\n",
    "                            matrix[x][y]=step\n",
    "                            tem.append((x,y))\n",
    "            step+=1\n",
    "        return matrix\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class ArrayQueue:\n",
    "    DEFAULT_CAPACITY=10\n",
    "    def __init__(self):\n",
    "        self._data=[(None,)]*ArrayQueue.DEFAULT_CAPACITY\n",
    "        self._size=0\n",
    "        self._front=0\n",
    "\n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self._size==0\n",
    "\n",
    "    def first(self):\n",
    "        if self.isEmpty():\n",
    "            return '队列为空'\n",
    "        return self._data[self._front]\n",
    "\n",
    "    def dequeue(self):\n",
    "        if self.isEmpty():\n",
    "            return '队列为空'\n",
    "        result=self._data[self._front]\n",
    "        self._data[self._front]=None\n",
    "        self._front=(self._front+1)%len(self._data)\n",
    "        self._size-=1\n",
    "        if 0<self._size<len(self._data)//4:\n",
    "            self._resize(len(self._data)//2)\n",
    "\n",
    "        return result\n",
    "\n",
    "    def _resize(self,cap):\n",
    "        old=self._data\n",
    "        self._data=[None]*cap\n",
    "        walk=self._front\n",
    "        for k in range(self._size):\n",
    "            self._data[k]=old[walk]\n",
    "            walk=(1+walk)%len(old)\n",
    "        self._front=0\n",
    "\n",
    "    def enqueue(self,e):\n",
    "        if self._size==len(self._data):\n",
    "            self._resize(2*len(self._data))\n",
    "\n",
    "        location=(self._front+self._size)%len(self._data)\n",
    "        self._data[location]=e\n",
    "        self._size+=1\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self,matrix,row,col):\n",
    "        while not self.queue.isEmpty():\n",
    "            loca_x,loca_y=self.queue.dequeue()\n",
    "            if loca_x-1>=0:\n",
    "                neighbor=matrix[loca_x-1][loca_y]\n",
    "                now=matrix[loca_x][loca_y]\n",
    "\n",
    "                if neighbor>now+1:\n",
    "                    matrix[loca_x-1][loca_y]=now+1\n",
    "                    self.queue.enqueue((loca_x-1,loca_y))\n",
    "\n",
    "            if loca_x+1<row:\n",
    "                neighbor = matrix[loca_x + 1][loca_y]\n",
    "                now = matrix[loca_x][loca_y]\n",
    "\n",
    "                if neighbor > now+1:\n",
    "                    matrix[loca_x + 1][loca_y] = now + 1\n",
    "                    self.queue.enqueue((loca_x+1,loca_y))\n",
    "\n",
    "            if loca_y-1>=0:\n",
    "                neighbor = matrix[loca_x][loca_y-1]\n",
    "                now = matrix[loca_x][loca_y]\n",
    "\n",
    "                if neighbor > now+1:\n",
    "                    matrix[loca_x][loca_y-1] = now + 1\n",
    "                    self.queue.enqueue((loca_x,loca_y-1))\n",
    "\n",
    "            if loca_y+1<col:\n",
    "                neighbor = matrix[loca_x][loca_y + 1]\n",
    "                now = matrix[loca_x][loca_y]\n",
    "\n",
    "                if neighbor > now+1:\n",
    "                    matrix[loca_x][loca_y + 1] = now + 1\n",
    "                    self.queue.enqueue((loca_x,loca_y+1))\n",
    "\n",
    "\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        row=len(matrix)\n",
    "        col=len(matrix[0])\n",
    "        self.queue=ArrayQueue()\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if matrix[i][j]==0:\n",
    "                    self.queue.enqueue((i,j))\n",
    "                else:\n",
    "                    matrix[i][j]=math.inf\n",
    "\n",
    "\n",
    "        self.bfs(matrix,row,col)\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        directs = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "                else:\n",
    "                    matrix[i][j] = sys.maxsize\n",
    "\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            for dx, dy in directs:\n",
    "                tx, ty = x + dx, y + dy\n",
    "                if 0 <= tx < m and 0 <= ty < n and matrix[tx][ty] > matrix[x][y] + 1:\n",
    "                    queue.append((tx, ty))\n",
    "                    matrix[tx][ty] = matrix[x][y] + 1\n",
    "\n",
    "        return matrix\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        \n",
    "        for i in range(0, row):\n",
    "            for j in range(0, col):\n",
    "                if matrix[i][j] == 1:\n",
    "                    matrix[i][j] = row + col\n",
    "                if i > 0:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i-1][j]+1)\n",
    "                if j > 0:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i][j-1]+1)\n",
    "        for i in range(row-1, -1, -1):\n",
    "            for j in range(col-1, -1, -1):\n",
    "                if i < row - 1:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i+1][j]+1)\n",
    "                if j < col - 1:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i][j+1]+1)\n",
    "        \n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if matrix == []:\n",
    "            return []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[float('inf')] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i > 0:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)\n",
    "                    if j > 0:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)\n",
    "                        \n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if matrix[i][j] == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i < m - 1:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1)\n",
    "                    if j < n - 1:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1)\n",
    "        return dp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        Q = []\n",
    "        visited = set()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    Q.append((i, j))\n",
    "                    visited.add((i, j))\n",
    "        \n",
    "        while Q:\n",
    "            i, j = Q.pop(0)\n",
    "            for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in visited:\n",
    "                    matrix[x][y] = matrix[i][j] + 1\n",
    "                    visited.add((x, y))\n",
    "                    Q.append((x, y))\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return []\n",
    "        n = len(matrix[0])\n",
    "        if n == 0:\n",
    "            return []\n",
    "\n",
    "        def BFS(matrix, i, j):\n",
    "            distance = 0\n",
    "            visit, queue = {(i, j)}, deque([(i, j)])\n",
    "            while queue:\n",
    "                size = len(queue)\n",
    "                for _ in range(size):\n",
    "                    x, y = queue.popleft()\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        if matrix[x][y] == 0:\n",
    "                            ans[i][j] = distance\n",
    "                            return\n",
    "                        visit.add((x, y))\n",
    "                        queue.extend([\n",
    "                            (x - 1, y), (x + 1, y),\n",
    "                            (x, y - 1), (x, y + 1)\n",
    "                        ])\n",
    "                distance += 1\n",
    "\n",
    "        ans = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    continue\n",
    "                BFS(matrix, i, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        Q = collections.deque([])\n",
    "        visited = set()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    Q.append((i,j))\n",
    "                    visited.add((i,j))\n",
    "        while Q :\n",
    "            i,j = Q.popleft()\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:\n",
    "                if 0 <= x < m and 0<= y <n and (x,y) not in visited:\n",
    "                    matrix[x][y] = matrix[i][j] + 1\n",
    "                    visited.add((x,y))\n",
    "                    Q.append((x,y))\n",
    "        return matrix\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if len(matrix)==0 or len(matrix[0])==0:\n",
    "            return matrix\n",
    "        \n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        \n",
    "        area=m*n\n",
    "        \n",
    "        dp=[[0 for j in range(n)] for i in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==0:\n",
    "                    dp[i][j]=0\n",
    "                else:\n",
    "                    up,left=area,area\n",
    "                    if i>0:\n",
    "                        up=dp[i-1][j]\n",
    "                    if j>0:\n",
    "                        left=dp[i][j-1]\n",
    "                    dp[i][j]=min(up+1,left+1)\n",
    "                    \n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if matrix[i][j]==0:\n",
    "                    dp[i][j]=0\n",
    "                else:\n",
    "                    down,right=area,area\n",
    "                    if i<m-1:\n",
    "                        down=dp[i+1][j]\n",
    "                    if j<n-1:\n",
    "                        right=dp[i][j+1]\n",
    "                    dp[i][j]=min(down+1,right+1,dp[i][j])\n",
    "                    \n",
    "        return dp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        # if len(matrix) == 0:return []\n",
    "        refresh = []\n",
    "        c = 0\n",
    "        l = len(matrix)\n",
    "        h = len(matrix[0])\n",
    "\n",
    "        res = [[10000 for i in range(h)] for j in range(l)]\n",
    "        for k, i in enumerate(matrix):\n",
    "            for kk, j in enumerate(i):\n",
    "                if j == 0:\n",
    "                    c += 1\n",
    "                    refresh.append([k, kk])\n",
    "                    res[k][kk]=0\n",
    "\n",
    "        while c < h * l:\n",
    "            now = refresh.pop(0)\n",
    "            k = now[0]\n",
    "            kk = now[1]\n",
    "            re = res[k][kk] + 1\n",
    "            if k > 0 and res[k - 1][kk]>re:\n",
    "                res[k - 1][kk] = re\n",
    "                refresh.append([k-1, kk])\n",
    "                c += 1\n",
    "            if k < l - 1 and res[k + 1][kk]> re:\n",
    "                res[k + 1][kk] = re\n",
    "                c += 1\n",
    "                refresh.append([k+1, kk])\n",
    "            if kk > 0 and  res[k][kk - 1]> re:\n",
    "                res[k][kk - 1] = re\n",
    "                c += 1\n",
    "                refresh.append([k, kk-1])\n",
    "            if kk < h - 1 and res[k][kk + 1]> re:\n",
    "                res[k][kk + 1] = re\n",
    "                c += 1\n",
    "                refresh.append([k, kk+1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        result = [[10000 for j in range(n)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    result[i][j] = 0\n",
    "        num = 0\n",
    "        flag = 1\n",
    "        while flag:\n",
    "            flag = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if result[i][j] == num:\n",
    "                        if i > 0:\n",
    "                            result[i - 1][j] = min(num + 1, result[i - 1][j])\n",
    "                        if i < m - 1:\n",
    "                            result[i + 1][j] = min(num + 1, result[i + 1][j])\n",
    "                        if j > 0:\n",
    "                            result[i][j - 1] = min(num + 1, result[i][j - 1])\n",
    "                        if j < n - 1:\n",
    "                            result[i][j + 1] = min(num + 1, result[i][j + 1])\n",
    "                    if result[i][j] == 10000:\n",
    "                        flag = 1\n",
    "            num += 1\n",
    "        return result\n",
    "                            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        rows = len(matrix)\n",
    "        if rows == 0:\n",
    "            return []\n",
    "        cols = len(matrix[0])\n",
    "        if cols == 0:\n",
    "            return [[]]\n",
    "        ret = [[100000] * cols for _ in range(rows)]\n",
    "        v = [[False] * cols for _ in range(rows)]\n",
    "        q = []\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if matrix[r][c] == 0:\n",
    "                    q.append((r, c))\n",
    "                    v[r][c] = True\n",
    "                    ret[r][c] = 0\n",
    "        det = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        while len(q) > 0:\n",
    "            new_q = []\n",
    "            for i in q:\n",
    "                r, c = i\n",
    "                for dr, dc in det:\n",
    "                    if (0 <= r + dr < rows) and (0 <= c + dc < cols) and not v[r + dr][c + dc]:\n",
    "                        v[r + dr][c + dc] = True\n",
    "                        ret[r + dr][c + dc] = min(ret[r + dr][c + dc], ret[r][c] + 1)\n",
    "                        new_q.append((r + dr, c + dc))\n",
    "            q = new_q\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode-cn.com/problems/01-matrix/description/\n",
    "from queue import PriorityQueue\n",
    "\n",
    "\n",
    "class Node(object):\n",
    "    position = None\n",
    "    weight = None\n",
    "\n",
    "    def __init__(self, position, weight):\n",
    "        self.position = position\n",
    "        self.weight = weight\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.weight < other.weight\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.weight == other.weight\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        if not matrix or not matrix[0]:\n",
    "            return matrix\n",
    "\n",
    "        marked = set()\n",
    "        pQueue = PriorityQueue()\n",
    "\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, val in enumerate(row):\n",
    "                if val == 0:\n",
    "                    pQueue.put(Node((i, j), 0))\n",
    "                else:\n",
    "                    matrix[i][j] = float('+inf')\n",
    "\n",
    "        while not pQueue.empty():\n",
    "            node = pQueue.get()\n",
    "            position = node.position\n",
    "            if position in marked:\n",
    "                continue\n",
    "            marked.add(position)\n",
    "\n",
    "            weight = node.weight\n",
    "            positions = [(position[0] - 1, position[1]),\n",
    "                         (position[0] + 1, position[1]),\n",
    "                         (position[0], position[1] - 1),\n",
    "                         (position[0], position[1] + 1)]\n",
    "            positions = [position for position in positions if 0 <= position[0] < m and 0 <= position[1] < n]\n",
    "\n",
    "            for p in positions:\n",
    "                if p in marked:\n",
    "                    continue\n",
    "\n",
    "                if weight + 1 < matrix[p[0]][p[1]]:\n",
    "                    matrix[p[0]][p[1]] = weight + 1\n",
    "                pQueue.put(Node(p, matrix[p[0]][p[1]]))\n",
    "\n",
    "        return matrix\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                l,t= 10001,10001\n",
    "                if matrix[i][j] != 0:\n",
    "                    if i > 0:\n",
    "                        t = matrix[i - 1][j]\n",
    "                    \n",
    "                    if j > 0:\n",
    "                        l = matrix[i][j - 1]\n",
    "                    \n",
    "                    matrix[i][j] = min(l,t) + 1\n",
    "        \n",
    "        for i in range(len(matrix) - 1, -1 ,-1):\n",
    "            for j in range(len(matrix[0]) - 1, -1, -1):\n",
    "                r,b = 10001,10001\n",
    "                if matrix[i][j] != 0:\n",
    "                    if i < len(matrix) - 1:\n",
    "                        b = matrix[i + 1][j]\n",
    "\n",
    "                    if j < len(matrix[0]) - 1:\n",
    "                        r = matrix[i][j + 1]\n",
    "\n",
    "                    matrix[i][j] = min(matrix[i][j], min(r,b) + 1)\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                up = 100000\n",
    "                left = 100000\n",
    "                if matrix[i][j]!= 0 :\n",
    "                    if i>0:\n",
    "                        up = matrix[i-1][j]\n",
    "                    if j>0:\n",
    "                        left = matrix[i][j-1]\n",
    "                    matrix[i][j] = min(up,left) +1\n",
    "        \n",
    "        for i in range(len(matrix)-1,-1,-1):\n",
    "            for j in range(len(matrix[0])-1,-1,-1):\n",
    "                down = 100000\n",
    "                right = 100000\n",
    "                if matrix[i][j]!= 0 :\n",
    "                    if i<len(matrix)-1:\n",
    "                        down = matrix[i+1][j]\n",
    "                    if j<len(matrix[0])-1:\n",
    "                        right = matrix[i][j+1]\n",
    "                    matrix[i][j] =min(matrix[i][j], min(down,right) +1)    \n",
    "        return matrix        \n",
    "        # import numpy\n",
    "        # from collections import deque\n",
    "        # dis = numpy.zeros((len(matrix),len(matrix[0])),dtype = numpy.int)\n",
    "        # for i in range(len(matrix)):\n",
    "        #     for j in range(len(matrix[0])):\n",
    "        #         queue = deque([[i,j]])\n",
    "        #         step = 0\n",
    "        #         if matrix[i][j] == 0:\n",
    "        #             dis[i][j] = 0\n",
    "        #         else:   \n",
    "        #             flage = False\n",
    "        #             while(queue and not flage):\n",
    "        #                 l = len(queue)\n",
    "        #                 step +=1\n",
    "        #                 for _ in range(l):\n",
    "        #                     cur = queue.pop()\n",
    "        #                     if cur[0] > 0 :\n",
    "        #                         cur_next = [cur[0]-1,cur[1]]\n",
    "        #                         if matrix[cur_next[0]][cur_next[1]] == 0:\n",
    "        #                             dis[i][j] = step\n",
    "        #                             flage = True\n",
    "        #                             break\n",
    "        #                         else:\n",
    "        #                             queue.appendleft(cur_next)\n",
    "        #                     if cur[0] < len(matrix)-1:\n",
    "        #                         cur_next = [cur[0]+1,cur[1]]\n",
    "        #                         if matrix[cur_next[0]][cur_next[1]]==0:\n",
    "        #                             dis[i,j] = step\n",
    "        #                             flage = True\n",
    "        #                             break\n",
    "        #                         else:\n",
    "        #                             queue.appendleft(cur_next)\n",
    "        #                     if cur[1] > 0:\n",
    "        #                         cur_next = [cur[0],cur[1]-1]\n",
    "        #                         if matrix[cur_next[0]][cur_next[1]]==0:\n",
    "        #                             dis[i][j] = step\n",
    "        #                             flage = True\n",
    "        #                             break\n",
    "        #                         else:\n",
    "        #                             queue.appendleft(cur_next)\n",
    "\n",
    "        #                     if cur[1] < len(matrix[0])-1:\n",
    "        #                         cur_next = [cur[0],cur[1]+1]\n",
    "        #                         if matrix[cur_next[0]][cur_next[1]] == 0:\n",
    "        #                             dis[i][j] = step\n",
    "        #                             flage = True\n",
    "        #                             break\n",
    "        #                         else:\n",
    "        #                             queue.appendleft(cur_next)\n",
    "        # return dis.tolist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        dirct=[[0,-1],[1,0],[0,1],[-1,0]]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]==0:\n",
    "                    continue\n",
    "                else:\n",
    "                    num=0\n",
    "                    q=[[i,j,num]]\n",
    "                    while q:\n",
    "                        c=q.pop(0)\n",
    "                        num =c[2]+ 1\n",
    "                        for o in dirct:\n",
    "                            if 0<=o[0]+c[0]<=len(matrix)-1 and 0<=o[1]+c[1]<=len(matrix[0])-1:\n",
    "                               q.append([o[0]+c[0],o[1]+c[1],num])\n",
    "                        if matrix[c[0]][c[1]] == 0:\n",
    "                            matrix[i][j]=c[2]\n",
    "                            break\n",
    "        return matrix\n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        from collections import deque\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        directions=[(-1,0),(1,0),(0,1),(0,-1)]\n",
    "        \n",
    "        res=matrix\n",
    "\n",
    "        def Is(x,y):\n",
    "            return x>=0 and x<m and y>=0 and y<n\n",
    "\n",
    "        def bfs(x,y):\n",
    "            queue=deque([(x,y,0)])\n",
    "            visited=set([(x,y)])\n",
    "            while queue:\n",
    "                i,j,dis=queue.popleft()\n",
    "                for direction in directions:\n",
    "                    new_i,new_j=i+direction[0],j+direction[1]\n",
    "                    if Is(new_i,new_j) and (new_i,new_j) not in visited:\n",
    "                        visited.add((new_i,new_j))\n",
    "                        if matrix[new_i][new_j]==0:\n",
    "                            return dis+1\n",
    "                        queue.append((new_i,new_j,dis+1))\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if res[i][j]==1:\n",
    "                    res[i][j]=bfs(i,j)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        dij = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        ra = len(matrix)\n",
    "        co = len(matrix[0])\n",
    "        que = []\n",
    "        \n",
    "        for i in range(ra):\n",
    "            for j in range(co):\n",
    "                if matrix[i][j]:\n",
    "                    mi = min(matrix[ni][nj] for ni,nj in filter(lambda x: -1<x[0]<ra and -1<x[1]<co, ((i+di,j+dj) for di, dj in dij)))\n",
    "                    if matrix[i][j] == mi:\n",
    "                        que.append((i, j))\n",
    "        while que:\n",
    "            tmp = []\n",
    "            for i,j in que:\n",
    "                matrix[i][j] += 1\n",
    "                \n",
    "            for i,j in que:\n",
    "                mi = min(matrix[ni][nj] for ni,nj in filter(lambda x: -1<x[0]<ra and -1<x[1]<co, ((i+di,j+dj) for di, dj in dij)))\n",
    "                if matrix[i][j] == mi:\n",
    "                    tmp.append((i, j))\n",
    "            que = tmp\n",
    "            \n",
    "        return matrix\n",
    "\n",
    "#     def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "#         ra = len(matrix)\n",
    "#         co = len(matrix[0])\n",
    "#         for i in range(ra):\n",
    "#             for j in range(co):\n",
    "#                 matrix[i][j] = min(matrix[i-1][j]+1 if i else 10001, matrix[i][j-1]+1 if j else 10001) if matrix[i][j] else 0\n",
    "\n",
    "#         for i in range(ra-1,-1,-1):\n",
    "#             for j in range(co-1,-1,-1):\n",
    "#                 matrix[i][j] = min(matrix[i+1][j]+1 if i<ra-1 else 10001, matrix[i][j+1]+1 if j<co-1 else 10001,matrix[i][j]) if matrix[i][j] else 0\n",
    "#         return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                l,t= 10001,10001\n",
    "                if matrix[i][j] != 0:\n",
    "                    if i > 0:\n",
    "                        t = matrix[i - 1][j]\n",
    "                    \n",
    "                    if j > 0:\n",
    "                        l = matrix[i][j - 1]\n",
    "                    \n",
    "                    matrix[i][j] = min(l,t) + 1\n",
    "        \n",
    "        for i in range(len(matrix) - 1, -1 ,-1):\n",
    "            for j in range(len(matrix[0]) - 1, -1, -1):\n",
    "                r,b = 10001,10001\n",
    "                if matrix[i][j] != 0:\n",
    "                    if i < len(matrix) - 1:\n",
    "                        b = matrix[i + 1][j]\n",
    "\n",
    "                    if j < len(matrix[0]) - 1:\n",
    "                        r = matrix[i][j + 1]\n",
    "\n",
    "                    matrix[i][j] = min(matrix[i][j], min(r,b) + 1)\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        \n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if matrix[i][j]:\n",
    "                    matrix[i][j] = rows + cols\n",
    "                if i > 0:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i-1][j]+1) #up\n",
    "                if j > 0:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i][j-1]+1) #left\n",
    "        \n",
    "        for i in range(rows-1, -1, -1):\n",
    "            for j in range(cols-1, -1, -1):\n",
    "                if i < rows - 1:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i+1][j]+1) #down\n",
    "                if j < cols - 1:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i][j+1]+1) #right\n",
    "        \n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        if not matrix:\n",
    "            return []\n",
    "        Maxlength = len(matrix) + len(matrix[0]) - 2\n",
    "        count = 0\n",
    "        \"\"\"0的四周的值赋值1（只要它不是0），\n",
    "        1的四周赋值2（只要它不是1，0）\n",
    "        假设一个n*n矩阵,距离上限为长+宽-2\"\"\"\n",
    "        def fun(i,j,n):\n",
    "            \"\"\"i,j:行和列\n",
    "            n:当前值\n",
    "            这个函数会将matrix[i][j]四周的值+1\"\"\"\n",
    "            count = 0\n",
    "            if i-1 >= 0 and matrix[i-1][j] > n+1:\n",
    "                matrix[i-1][j] = n+1\n",
    "                count += 1\n",
    "            if i+1 < len(matrix) and matrix[i+1][j] > n+1:\n",
    "                matrix[i+1][j] = n+1\n",
    "                count += 1\n",
    "            if j-1 >= 0 and matrix[i][j-1] > n+1:\n",
    "                matrix[i][j-1] = n+1\n",
    "                count += 1\n",
    "            if j+1 < len((matrix[0])) and matrix[i][j+1] > n+1:\n",
    "                matrix[i][j+1] = n+1\n",
    "                count += 1\n",
    "            return count\n",
    "\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] != 0:\n",
    "                    matrix[i][j] = Maxlength + 1\n",
    "                    count += 1\n",
    "        for n in range(Maxlength):\n",
    "            for i in range(len(matrix)):\n",
    "                for j in range(len(matrix[0])):\n",
    "\n",
    "                    if matrix[i][j] == n:\n",
    "                        count -= fun(i, j, n)\n",
    "                    if count == 0:\n",
    "                        return matrix\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        max_dis = m*n\n",
    "        # dp = [[max_dis if mat[i][j] != 0 else 0 for j in range(n)] for i in range(m)]\n",
    "        dp = mat\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp[i][j] != 0:\n",
    "                    dp[i][j] = max_dis\n",
    "        # 从 i, j 向左上方寻找 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp[i][j] == 0:\n",
    "                    continue\n",
    "                if i > 0:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][j]+1)\n",
    "                if j > 0:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][j-1]+1)\n",
    "        \n",
    "        # 从 i, j 向右下方寻找 0\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if dp[i][j] == 0:\n",
    "                    continue\n",
    "                if i < m-1:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i+1][j]+1)\n",
    "                if j < n-1:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][j+1]+1)\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    mat[i][j] = 9999999\n",
    "        for i in range(m):\n",
    "            for j in range(1,n):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] =  mat[i][j-1] + 1\n",
    "        for i in range(m):\n",
    "            for j in range(n-2,0,-1):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] =  min(mat[i][j+1] + 1, mat[i][j])\n",
    "            else:\n",
    "                if mat[i][0] != 0 and n > 1:\n",
    "                    mat[i][0] =  mat[i][1] + 1\n",
    "        for j in range(n):\n",
    "            for i in range(1,m):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] =  min(mat[i-1][j] + 1, mat[i][j])\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(m-2,-1,-1):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] =  min(mat[i+1][j] + 1, mat[i][j])\n",
    "\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        MAX = 1e6\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                \n",
    "                if mat[i][j] == 1:\n",
    "                    mat[i][j] = MAX\n",
    "\n",
    "                if i > 0:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i - 1][j] + 1)\n",
    "                if j > 0:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i][j - 1] + 1)\n",
    "        \n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                \n",
    "                if i < m - 1:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i + 1][j] + 1)\n",
    "                if j < n - 1:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i][j + 1] + 1)\n",
    "\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        coj = len(mat[0])\n",
    "        for i in range(row):\n",
    "            for j in range(coj):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] = 10000000\n",
    "                    if i - 1 >= 0:\n",
    "                        mat[i][j] = min(mat[i - 1][j] + 1, mat[i][j])\n",
    "                    if j - 1 >= 0:\n",
    "                        mat[i][j] = min(1 + mat[i][j - 1], mat[i][j])\n",
    "        for i in range(row)[::-1]:\n",
    "            for j in range(coj)[::-1]:\n",
    "                if mat[i][j] == 0:\n",
    "                    continue\n",
    "                if i + 1 < row:\n",
    "                    mat[i][j] = min(mat[i][j], 1 + mat[i + 1][j])\n",
    "                if j + 1 < coj:\n",
    "                    mat[i][j] = min(mat[i][j], 1 + mat[i][j + 1])\n",
    "        return mat\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] = float('inf') if mat[i][j] else 0\n",
    "        \n",
    "        # 左上角往下\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i - 1][j] + 1)\n",
    "                if j > 0:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i][j - 1] + 1)\n",
    "        \n",
    "        # 右下角往上\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i < m - 1:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i + 1][j] + 1)\n",
    "                if j < n - 1:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i][j + 1] + 1)\n",
    "\n",
    "        return mat\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    queue.append([i, j])\n",
    "                else:\n",
    "                    mat[i][j] = inf\n",
    "        d = [[0, 1],[0,-1],[1,0],[-1,0]]\n",
    "        t = 1\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            for i in range(l):\n",
    "                cur = queue.pop(0)\n",
    "                for i in range(4):\n",
    "                    nx, ny = cur[0] + d[i][0], cur[1] + d[i][1]\n",
    "                    if nx < 0 or nx >= m or ny < 0 or ny >= n or mat[nx][ny] == 0 or t > mat[nx][ny]:\n",
    "                        continue\n",
    "                    mat[nx][ny] = t\n",
    "                    queue.append([nx, ny])\n",
    "            t += 1\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        # 多源BFS\n",
    "        # 找每个1到最近0的距离\n",
    "        def inArea(mat, r, c):\n",
    "            return r>=0 and r<len(mat) and c>=0 and c<len(mat[0])\n",
    "        \n",
    "        # 将所有0入队\n",
    "        # 直接在mat上记录结果，将所有1设为-1，表示没有被访问的结点和0点\n",
    "        q = []\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append([i, j])\n",
    "                else:\n",
    "                    mat[i][j] = -1\n",
    "        \n",
    "        adjs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        while q!= []:\n",
    "            node = q.pop(0)\n",
    "            r, c = node\n",
    "            # mat[r][c] += 1\n",
    "            for adj in adjs:\n",
    "                r2 = r + adj[0]\n",
    "                c2 = c + adj[1]\n",
    "                if inArea(mat, r2, c2) and mat[r2][c2] == -1:\n",
    "                    mat[r2][c2] = mat[r][c] + 1\n",
    "                    q.append([r2, c2])\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        #copy\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                l,t= 10001,10001\n",
    "                if mat[i][j] != 0:\n",
    "                    if i >0 :\n",
    "                        t= mat[i-1][j]\n",
    "                    if j >0:\n",
    "                        l = mat[i][j-1]\n",
    "                    mat[i][j] = min(l,t) + 1\n",
    "        \n",
    "        for i in range(len(mat)-1,-1,-1):\n",
    "            for j in range(len(mat[0])-1,-1,-1):\n",
    "                r,b= 10001,10001\n",
    "                if mat[i][j] != 0:\n",
    "                    if i <len(mat)-1:\n",
    "                        b = mat[i+1][j]\n",
    "                    if j <len(mat[0])-1:\n",
    "                        r = mat[i][j+1]\n",
    "                    mat[i][j] = min(mat[i][j],min(r,b)+1)\n",
    "        return mat\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                l,t= 10001,10001\n",
    "                if mat[i][j] != 0:\n",
    "                    if i > 0:\n",
    "                        t = mat[i - 1][j]\n",
    "                    \n",
    "                    if j > 0:\n",
    "                        l = mat[i][j - 1]\n",
    "                    \n",
    "                    mat[i][j] = min(l,t) + 1\n",
    "        print(mat)\n",
    "        \n",
    "        for i in range(len(mat) - 1, -1 ,-1):\n",
    "            for j in range(len(mat[0]) - 1, -1, -1):\n",
    "                r,b = 10001,10001\n",
    "                if mat[i][j] != 0:\n",
    "                    if i < len(mat) - 1:\n",
    "                        b = mat[i + 1][j]\n",
    "\n",
    "                    if j < len(mat[0]) - 1:\n",
    "                        r = mat[i][j + 1]\n",
    "\n",
    "                    mat[i][j] = min(mat[i][j], min(r,b) + 1)\n",
    "        print(mat)\n",
    "        return mat\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        每个0向四周扩散 进行BFS搜索\n",
    "        \"\"\"\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        queue = deque()\n",
    "        dirs = [(0,-1),(0,1),(1,0),(-1,0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append((i,j))\n",
    "                else:\n",
    "                    mat[i][j] = -1 #代表还未被访问\n",
    "        while queue:\n",
    "            x,y = queue.popleft()\n",
    "            for dx,dy in dirs:\n",
    "                new_x,new_y = x+dx,y+dy\n",
    "                if 0<=new_x<m and 0<=new_y<n and mat[new_x][new_y]==-1:\n",
    "                    mat[new_x][new_y] = mat[x][y]+1\n",
    "                    queue.append((new_x,new_y))\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        directions=[(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        queue=deque([])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append((i,j))\n",
    "                else:\n",
    "                    mat[i][j]=-1\n",
    "\n",
    "        while queue:\n",
    "            x,y=queue.popleft()\n",
    "            for deltaX,deltaY in directions:\n",
    "                newX=x+deltaX\n",
    "                newY=y+deltaY\n",
    "                if 0<=newX<m and 0<=newY<n and mat[newX][newY]==-1:\n",
    "                    mat[newX][newY]=mat[x][y]+1\n",
    "                    queue.append((newX,newY))\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        # 初始化动态规划的数组，所有的距离值都设置为一个很大的数\n",
    "        dist = [[10**9] * n for _ in range(m)]\n",
    "        # 如果 (i, j) 的元素为 0，那么距离为 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    dist[i][j] = 0\n",
    "        # 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)\n",
    "                if j - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)\n",
    "        # 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n):\n",
    "                if i + 1 < m:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)\n",
    "                if j - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)\n",
    "        # 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序\n",
    "        for i in range(m):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)\n",
    "                if j + 1 < n:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)\n",
    "        # 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i + 1 < m:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)\n",
    "                if j + 1 < n:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        col = len(mat[0])\n",
    "        dp = [[float('inf')]*col for _ in range(row)]\n",
    "\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if mat[r][c] == 0:\n",
    "                    dp[r][c] = 0\n",
    "                else:\n",
    "                    up = dp[r-1][c] if r-1 >= 0 else float('inf')\n",
    "                    left = dp[r][c-1] if c-1 >= 0 else float('inf')\n",
    "                    dp[r][c] = min(up, left) + 1\n",
    "\n",
    "        \n",
    "        for r in range(row-1, -1, -1):\n",
    "            for c in range(col-1, -1, -1):\n",
    "                if mat[r][c] == 0:\n",
    "                    dp[r][c] = 0\n",
    "                else:\n",
    "                    down = dp[r+1][c] if r+1 < row else float('inf')\n",
    "                    right = dp[r][c+1] if c+1 < col else float('inf')\n",
    "                    dp[r][c] = min(min(down, right) + 1, dp[r][c])\n",
    "        \n",
    "        return dp\n",
    "                \n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        x_len = len(mat)\n",
    "        y_len = len(mat[0])\n",
    "        ans = [[None] * y_len for _ in range(x_len)]\n",
    "\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for x in range(x_len):\n",
    "            for y in range(y_len):\n",
    "                if mat[x][y] == 0:\n",
    "                    ans[x][y] = 0\n",
    "                    queue.append((x,y))\n",
    "\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            for dif_x, dif_y in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                next_x, next_y = dif_x + x, dif_y + y\n",
    "                if 0<=next_x<x_len and 0<=next_y<y_len and ans[next_x][next_y] == None:\n",
    "                    ans[next_x][next_y] = ans[x][y] + 1\n",
    "                    queue.append((next_x, next_y))\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        max_x = len(mat)\n",
    "        max_y = len(mat[0])\n",
    "\n",
    "        result = [[None for x in range(max_y)] for x in range(max_x)]\n",
    "\n",
    "        q = collections.deque()\n",
    "\n",
    "        for i in range(max_x):\n",
    "            for j in range(max_y):\n",
    "                if mat[i][j] == 0:\n",
    "                    result[i][j] = 0\n",
    "                    q.append([i, j])\n",
    "\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x_bias, y_bias in  [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                new_x = i + x_bias\n",
    "                new_y = j + y_bias\n",
    "                if 0 <= new_x < max_x and 0 <= new_y < max_y and result[new_x][new_y] == None:\n",
    "                    result[new_x][new_y] = result[i][j] + 1\n",
    "                    q.append([new_x, new_y])\n",
    "\n",
    "        return result\n",
    "\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        每个0向四周扩散 进行BFS搜索\n",
    "        \"\"\"\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        seen = set()\n",
    "        queue = deque()\n",
    "        dirs = [(0,-1),(0,1),(1,0),(-1,0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append((i,j))\n",
    "                    seen.add((i,j))\n",
    "                    mat[i][j] = 2\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                x,y = queue.popleft()\n",
    "                for dx,dy in dirs:\n",
    "                    new_x,new_y = x+dx,y+dy\n",
    "                    if 0<=new_x<m and 0<=new_y<n and (new_x,new_y) not in seen:\n",
    "                        mat[new_x][new_y] = mat[x][y]+1\n",
    "                        queue.append((new_x,new_y))\n",
    "                        seen.add((new_x,new_y))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] -= 2\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        # def bfs(q, visited, step):\n",
    "        #     while q:\n",
    "        #         size = len(q)\n",
    "        #         for _ in range(size):\n",
    "        #             x, y = q.popleft()\n",
    "        #             for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):\n",
    "        #                 if nx < 0 or nx >= m or ny < 0 or ny >= n:\n",
    "        #                     continue\n",
    "        #                 if mat[nx][ny] == 0:\n",
    "        #                     return step\n",
    "        #                 if (nx, ny) not in visited:\n",
    "        #                     q.append((nx, ny))\n",
    "        #                     visited.add((nx, ny))       \n",
    "        #         step += 1\n",
    "\n",
    "        # m, n = len(mat), len(mat[0])\n",
    "        # ans = [[-1] * n for _ in range(m)]\n",
    "        \n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         ans[i][j] += 1\n",
    "        #         if mat[i][j] == 1:\n",
    "        #             q = deque()\n",
    "        #             visited = set()\n",
    "        #             q.append((i, j))\n",
    "        #             visited.add((i, j))\n",
    "                    \n",
    "        #             ans[i][j] = bfs(q, visited, 1)\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        queue = deque()\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "                    visited[i][j] = 1\n",
    "\n",
    "        step = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                x, y = queue.popleft()\n",
    "                if mat[x][y] == 1:\n",
    "                    res[x][y] = step\n",
    "                for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):\n",
    "                    if nx < 0 or nx >= m or ny < 0 or ny >= n or visited[nx][ny] == 1:\n",
    "                        continue\n",
    "                    queue.append((nx, ny))\n",
    "                    visited[nx][ny] = 1\n",
    "            step += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "                    \n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        '''\n",
    "        求节点i到 最近 的0的距离\n",
    "        适合bfs\n",
    "        如果是从节点1出发，每个节点1都跑一遍bfs，时间复杂度是O(m^2*n^2)\n",
    "        横看成岭侧成峰\n",
    "        如果是从多个节点0一起出发，只跑一遍bfs，这就可以保证正确性了，这也叫多源bfs\n",
    "        建立一个超级源点？？\n",
    "        '''\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        q=[]\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        for i,row in enumerate(mat):\n",
    "            for j,x in enumerate(row):\n",
    "                if not x:\n",
    "                    q.append((i,j))\n",
    "                    vis[i][j]=True\n",
    "        dist=0\n",
    "        while q:\n",
    "            dist+=1\n",
    "            tmp=[]\n",
    "            while q:\n",
    "                (x,y)=q.pop()\n",
    "                for i,j in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                    if 0<=i<m and 0<=j<n and not vis[i][j]:\n",
    "                        vis[i][j]=True\n",
    "                        tmp.append((i,j))\n",
    "                        ans[i][j]=dist\n",
    "            q=tmp\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        from collections import deque\n",
    "\n",
    "        nRow, nCol = len(mat), len(mat[0])\n",
    "\n",
    "        res = [[0 for _ in range(nCol)] for _ in range(nRow)]\n",
    "        visit = [[0 for _ in range(nCol)] for _ in range(nRow)]\n",
    "\n",
    "        queue = deque()\n",
    "\n",
    "        for r in range(len(mat)):\n",
    "            for c in range(len(mat[0])):\n",
    "                if mat[r][c] == 0:\n",
    "                    queue.append((r, c))\n",
    "                    visit[r][c] = 1\n",
    "                    \n",
    "        moves = [\n",
    "            [-1, 0],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [0, 1],\n",
    "        ]\n",
    "\n",
    "        step = 0\n",
    "        \n",
    "        while queue:\n",
    "\n",
    "            for _ in range(len(queue)):\n",
    "                \n",
    "                x, y = queue.popleft()\n",
    "\n",
    "                if mat[x][y] == 1:\n",
    "                    res[x][y] = step\n",
    "\n",
    "                for move in moves:\n",
    "                    \n",
    "                    new_x, new_y = x + move[0], y + move[1]\n",
    "                    \n",
    "                    if 0 <= new_x < len(mat) and 0 <= new_y < len(mat[0]) and visit[new_x][new_y] == 0:\n",
    "                        \n",
    "                        queue.append((new_x, new_y))\n",
    "                        visit[new_x][new_y] = 1\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "  ### 多源最短路问题思路比较固定，大概分为以下几步： 1，设目标数组和标记数组，标记该点是否被访问到 2，寻找一开始的“源\",放入队列，并且标记已经访问过 2.当队列非空的时候，每次找队头元素，（记得弹出队列）四个方向（有时候是 八个方向）广搜，先判断是否超出边界或者被访问过，如果没有就把该点标记为访问过，按照题目要求要处理一下（这里是标记距离），然后放入队列即可\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dist = [[0] * n for _ in range(m)]\n",
    "        zeroes_pos = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]\n",
    "        # 将所有的 0的下标 添加进初始队列中\n",
    "        q = collections.deque(zeroes_pos)\n",
    "        seen = set(zeroes_pos)\n",
    "\n",
    "        # 广度优先搜索\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:### 该点四个方向搜索\n",
    "                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen: ### 这些是没有处理过的1\n",
    "                    dist[ni][nj] = dist[i][j] + 1\n",
    "                    q.append((ni, nj)) ### 添加进来，准备在他周围继续搜索，\n",
    "                    ### 第一遍，所有的在0附近的1都搞完了\n",
    "                    ###继续pop，就会找到新的pop\n",
    "                    seen.add((ni, nj)) ### 已经处理过了\n",
    "        \n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        # num_infty = 0\n",
    "        # res = [[float(\"inf\") for _ in range(len(mat[0]))] for _ in range(len(mat))]   \n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] = float(\"inf\")\n",
    "\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] != 0:\n",
    "                    if i > 0: mat[i][j] = min(mat[i][j], mat[i-1][j] + 1)\n",
    "                    if j > 0: mat[i][j] = min(mat[i][j], mat[i][j-1] + 1)\n",
    "            \n",
    "        for i in range(len(mat)-1, -1, -1):\n",
    "            for j in range(len(mat[0])-1, -1, -1):\n",
    "                if mat[i][j] != 0:\n",
    "                    if i + 1 < len(mat): mat[i][j] = min(mat[i][j], mat[i+1][j] + 1)\n",
    "                    if j + 1 < len(mat[0]): mat[i][j] = min(mat[i][j], mat[i][j+1] + 1)\n",
    "            \n",
    "        return mat\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        col = len(mat[0])\n",
    "        dists = [[0]*col for _ in range(row)]\n",
    "        q = deque()\n",
    "        # 先初始化，0的距离就为0 1的赋大值\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append([i,j])\n",
    "                    dists[i][j]=0\n",
    "                else:\n",
    "                    dists[i][j] = 1e5\n",
    "        dirs = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        while q:\n",
    "            pos = q.popleft()\n",
    "            dist = dists[pos[0]][pos[1]]\n",
    "            for d in dirs:\n",
    "                r = pos[0]+d[0]\n",
    "                c = pos[1]+d[1]\n",
    "                if r>=0 and r<row and c>=0 and c<col:\n",
    "                    if dists[r][c]>dist+1:  #   就原本不是0 则重新赋值\n",
    "                        dists[r][c] = dist+1  \n",
    "                        q.append([r,c])\n",
    "        return dists\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        vis = [[False]*n for _ in range(m)]\n",
    "\n",
    "        #把0放入队列找周围的1，然后更改该数值，它外层数值依次依据当前值加1\n",
    "        #bfs\n",
    "        que = collections.deque()\n",
    "        direc = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0 and vis[i][j] == False:\n",
    "                    vis[i][j] = True\n",
    "                    que.append([i,j])\n",
    "\n",
    "        while que:\n",
    "            i,j = que.popleft()\n",
    "            for a,b in direc:\n",
    "                if 0<=i+a<m and 0<=b+j<n and vis[i+a][j+b]==False:\n",
    "                    mat[i+a][j+b] = mat[i][j] + 1\n",
    "                    vis[i+a][j+b] = True\n",
    "                    que.append([i+a,j+b]) \n",
    "        return mat\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        queue = deque([])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0: queue.append((i, j))\n",
    "                else: mat[i][j] = -1\n",
    "\n",
    "\n",
    "        while queue:\n",
    "            i, j = queue.popleft()\n",
    "            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):\n",
    "                if 0 <= x < m and 0 <= y < n and mat[x][y] == -1:\n",
    "                    mat[x][y] = mat[i][j] + 1\n",
    "                    queue.append((x, y))\n",
    "        \n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        zero = [(i,j) for i in range(m) for j in range(n) if mat[i][j]==0]\n",
    "        used = set(zero)\n",
    "        q = collections.deque(zero)\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:\n",
    "                if 0<=ni<m and 0<=nj<n and (ni,nj) not in used:\n",
    "                    used.add((ni,nj))\n",
    "                    q.append((ni,nj))\n",
    "                    mat[ni][nj] = mat[i][j]+1\n",
    "\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        step = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        ans = [[inf]*m for _ in range(n)]\n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j] == 0:\n",
    "                    ans[i][j] = 0\n",
    "                    queue.append([i,j,0])\n",
    "        while queue:\n",
    "            x,y,dis = queue.pop(0)\n",
    "            dis+=1\n",
    "            for dx,dy in step:\n",
    "                xx =x+dx\n",
    "                yy =dy+y\n",
    "                if 0<=xx<n and 0<=yy<m and ans[xx][yy]>dis :\n",
    "                    ans[xx][yy] = dis\n",
    "                    queue.append([xx,yy,dis])\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        dq = deque()\n",
    "        vis = set()\n",
    "        m,n  = len(mat), len(mat[0])\n",
    "        ans = mat.copy()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dq.append((i, j, 0))\n",
    "                    vis.add((i, j))\n",
    "\n",
    "        while dq:\n",
    "            x, y, val = dq[0]\n",
    "            ans[x][y] = val\n",
    "            dq.popleft()\n",
    "            for dx, dy in ((0,1), (1,0), (0,-1), (-1,0)):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis:\n",
    "                    dq.append((nx, ny, val+1))\n",
    "                    vis.add((nx, ny))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        ans = [[-1]*n for _ in range(m)]\n",
    "        q = []\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append((i, j))\n",
    "                    ans[i][j] = 0\n",
    "\n",
    "        DIRS = [[-1, 0], [0, -1], [+1, 0], [0, +1]]\n",
    "        d = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            d += 1\n",
    "            for i,j in tmp:\n",
    "                for dx, dy in DIRS:\n",
    "                    if 0<= i+dx <m and 0<= j+dy <n and ans[i+dx][j+dy] == -1:\n",
    "                        ans[i+dx][j+dy] = d\n",
    "                        q.append((i+dx, j+dy))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        queue = []\n",
    "        seen = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0: \n",
    "                    queue.append((i,j))\n",
    "                    seen.add((i,j))\n",
    "        queue = collections.deque(queue)\n",
    "        while queue:\n",
    "            # print(queue)\n",
    "            i,j = queue.popleft()\n",
    "            for ni,nj in (i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                if ni>=0 and ni<m and nj>=0 and nj<n and (ni,nj) not in seen:\n",
    "                    mat[ni][nj] = mat[i][j]+1\n",
    "                    queue.append((ni,nj))\n",
    "                    seen.add((ni,nj))\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[float(\"inf\")] * len(mat[idx]) for idx in range(len(mat))]\n",
    "\n",
    "        for idx in range(len(mat)):\n",
    "            for idy in range(len(mat[idx])):\n",
    "                if mat[idx][idy] == 0:\n",
    "                    res[idx][idy] = 0\n",
    "                else:\n",
    "                    if idx - 1 >= 0:\n",
    "                        if mat[idx - 1][idy] == 0:\n",
    "                            res[idx][idy] = 1\n",
    "                        else:\n",
    "                            res[idx][idy] = min(res[idx][idy], res[idx - 1][idy] + 1)\n",
    "                    if idy - 1 >= 0:\n",
    "                        if mat[idx][idy - 1] == 0:\n",
    "                            res[idx][idy] = 1\n",
    "                        else:\n",
    "                            res[idx][idy] = min(res[idx][idy], res[idx][idy - 1] + 1)\n",
    "\n",
    "        for idx in range(len(mat) - 1, -1, -1):\n",
    "            for idy in range(len(mat[idx]) - 1, -1, -1):\n",
    "                if mat[idx][idy] == 0:\n",
    "                    res[idx][idy] = 0\n",
    "                else:\n",
    "                    if idx + 1 < len(mat):\n",
    "                        if mat[idx + 1][idy] == 0:\n",
    "                            res[idx][idy] = 1\n",
    "                        else:\n",
    "                            res[idx][idy] = min(res[idx][idy], res[idx + 1][idy] + 1)\n",
    "                    if idy + 1 < len(mat[idx]):\n",
    "                        if mat[idx][idy + 1] == 0:\n",
    "                            res[idx][idy] = 1\n",
    "                        else:\n",
    "                            res[idx][idy] = min(res[idx][idy], res[idx][idy + 1] + 1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        stack = []\n",
    "        # 广度优先搜索\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    stack.append((i,j))\n",
    "                else:\n",
    "                    mat[i][j] = float('inf')\n",
    "        while stack:\n",
    "            x,y = stack.pop(0)\n",
    "            for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                nx,ny = x+dx,y+dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and mat[nx][ny] > mat[x][y] + 1:\n",
    "                    mat[nx][ny] = mat[x][y] + 1\n",
    "                    stack.append((nx, ny))\n",
    "        \n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        ## 从0开始向外BFS\n",
    "        visited = [[0] * len(mat[0]) for _ in range(len(mat))]\n",
    "        q = deque([])\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] == 0:\n",
    "                    visited[i][j] = 1\n",
    "                    q.append((i,j))\n",
    "        while q:\n",
    "            cur_x,cur_y = q.popleft()\n",
    "            for x,y in [(0,1),(1,0),(0,-1),(-1,0)]:\n",
    "                nxt_x,nxt_y = cur_x + x,cur_y + y\n",
    "                if 0 <= nxt_x < len(mat) and 0 <= nxt_y <len(mat[0]) and visited[nxt_x][nxt_y] == 0:\n",
    "                    mat[nxt_x][nxt_y] = mat[cur_x][cur_y] + 1\n",
    "                    q.append((nxt_x,nxt_y))\n",
    "                    visited[nxt_x][nxt_y] = 1\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        queue = []\n",
    "        for i in range(len(mat)):\n",
    "            res.append([])\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] == 0:\n",
    "                    res[i].append(0)\n",
    "                    queue.append([i, j])\n",
    "                else:\n",
    "                    res[i].append(-1)\n",
    "        dis = 1\n",
    "        while len(queue):\n",
    "            for i in range(len(queue)):\n",
    "                r = queue[0]\n",
    "                if r[0] > 0 and res[r[0] - 1][r[1]] == -1:\n",
    "                    res[r[0] - 1][r[1]] = dis\n",
    "                    queue.append([r[0] - 1, r[1]])\n",
    "                if r[0] < len(mat) - 1 and res[r[0] + 1][r[1]] == -1:\n",
    "                    res[r[0] + 1][r[1]] = dis\n",
    "                    queue.append([r[0] + 1, r[1]])\n",
    "                if r[1] > 0 and res[r[0]][r[1] - 1] == -1:\n",
    "                    res[r[0]][r[1] - 1] = dis\n",
    "                    queue.append([r[0], r[1] - 1])\n",
    "                if r[1] < len(mat[0]) - 1 and res[r[0]][r[1] + 1] == -1:\n",
    "                    res[r[0]][r[1] + 1] = dis\n",
    "                    queue.append([r[0], r[1] + 1])\n",
    "                queue.remove(r)\n",
    "            dis += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        res = [[100001]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j] == 0:\n",
    "                    res[i][j] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i > 0:\n",
    "                    res[i][j] = min(res[i-1][j]+1, res[i][j])\n",
    "                if j > 0:\n",
    "                    res[i][j] = min(res[i][j-1]+1, res[i][j])\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(m-1, -1, -1):\n",
    "                if i < n-1:\n",
    "                    res[i][j] = min(res[i+1][j]+1, res[i][j])\n",
    "                if j < m-1:\n",
    "                    res[i][j] = min(res[i][j+1]+1, res[i][j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    if i>0:\n",
    "                        if j>0:\n",
    "                            ans[i][j] = min(ans[i-1][j], ans[i][j-1]) + 1\n",
    "                        else:\n",
    "                            ans[i][j] = ans[i-1][j] + 1\n",
    "                    else:\n",
    "                        if j>0:\n",
    "                            ans[i][j] = ans[i][j-1] + 1\n",
    "                        else:\n",
    "                            ans[i][j] = 1e9\n",
    "\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if mat[i][j] == 1:\n",
    "                    if i<m-1:\n",
    "                        if j<n-1:\n",
    "                            ans[i][j] = min(ans[i][j], min(ans[i+1][j], ans[i][j+1])+1)\n",
    "                        else:\n",
    "                            ans[i][j] = min(ans[i][j], ans[i+1][j]+1)\n",
    "                    else:\n",
    "                        if j<n-1:\n",
    "                            ans[i][j] = min(ans[i][j], ans[i][j+1]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 初始化动态规划的数组，所有的距离值都设置为一个很大的数\n",
    "        dist = [[10**9] * n for _ in range(m)]\n",
    "        # 如果 (i, j) 的元素为 0，那么距离为 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dist[i][j] = 0\n",
    "        # 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)\n",
    "                if j - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)\n",
    "        # 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i + 1 < m:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)\n",
    "                if j + 1 < n:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        使用动态规划的思路求解\n",
    "        \"\"\"\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        ret = [[max(m,n)]*n for _ in range(m)]\n",
    "\n",
    "        # 先从左往右处理第一行\n",
    "        ret[0][0] = 0 if mat[0][0] == 0 else ret[0][0]\n",
    "        for j in range(1, n):\n",
    "            if mat[0][j] == 0:\n",
    "                ret[0][j] = 0\n",
    "            else:\n",
    "                ret[0][j] = min(ret[0][j], ret[0][j-1] + 1)\n",
    "\n",
    "        # 以左上到右下的顺序处理\n",
    "        for i in range(1, m):\n",
    "            if mat[i][0] == 0:\n",
    "                ret[i][0] = 0\n",
    "            else:\n",
    "                ret[i][0] = min(ret[i][0], ret[i-1][0] + 1)\n",
    "            for j in range(1, n):\n",
    "                if mat[i][j] == 0:\n",
    "                    ret[i][j] = 0\n",
    "                else:\n",
    "                    ret[i][j] = min(ret[i][j], ret[i-1][j]+1, ret[i][j-1]+1)\n",
    "        \n",
    "        # 从右往左处理最后一行\n",
    "        for j in range(n-2, -1, -1):\n",
    "            ret[m-1][j] = min(ret[m-1][j], ret[m-1][j+1]+1)\n",
    "        \n",
    "        # 以右下到左上的顺序处理\n",
    "        for i in range(m-2, -1, -1):\n",
    "            ret[i][n-1] = min(ret[i][n-1], ret[i+1][n-1] + 1)\n",
    "            for j in range(n-2, -1, -1):\n",
    "                ret[i][j] = min(ret[i][j], ret[i+1][j]+1, ret[i][j+1]+1)\n",
    "            \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        stack = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:  stack.append((i, j))\n",
    "        \n",
    "        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for x, y in stack:\n",
    "                for dx, dy in direction:\n",
    "                    X, Y = x + dx, y + dy\n",
    "                    if 0 <= X < m and 0 <= Y < n and mat[X][Y] == 1:\n",
    "                        mat[X][Y] = mat[x][y] - 1\n",
    "                        temp.append((X, Y))\n",
    "            stack = temp\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] *= -1\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[inf]*n for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0: dp[i][j]=0\n",
    "                else:\n",
    "                    if i==0 and j==0: continue\n",
    "                    elif i==0: dp[i][j] = min(dp[i][j], dp[i][j-1]+1)\n",
    "                    elif j==0: dp[i][j] = min(dp[i][j], dp[i-1][j]+1)\n",
    "                    else: dp[i][j] = min([dp[i][j], dp[i-1][j]+1, dp[i][j-1]+1])\n",
    "        \n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if mat[i][j]==0: dp[i][j]=0\n",
    "                else:\n",
    "                    if i==m-1 and j==n-1: continue\n",
    "                    elif i==m-1: dp[i][j] = min(dp[i][j], dp[i][j+1]+1)\n",
    "                    elif j==n-1: dp[i][j] = min(dp[i][j], dp[i+1][j]+1)\n",
    "                    else: dp[i][j] = min([dp[i][j], dp[i+1][j]+1, dp[i][j+1]+1])\n",
    "\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        # 不出意外的超时了\n",
    "        # n=len(mat)\n",
    "        # m=len(mat[0])\n",
    "        # # result[n][m]\n",
    "        # result=[[0]*m for _ in range(n)]\n",
    "        # def bfs(i,j):\n",
    "        #     queue=[(i,j,0)]\n",
    "        #     while queue:\n",
    "        #         node=queue.pop(0)\n",
    "        #         i,j,h=node[0],node[1],node[2]\n",
    "        #         if mat[i][j]==0:\n",
    "        #             return h\n",
    "        #         else:\n",
    "        #             if i+1<m:\n",
    "        #                 queue.append((i+1,j,h+1))\n",
    "        #             if 0<=i-1:\n",
    "        #                 queue.append((i-1,j,h+1))\n",
    "        #             if j+1<m:\n",
    "        #                 queue.append((i,j+1,h+1))\n",
    "        #             if 0<=j-1:\n",
    "        #                 queue.append((i,j-1,h+1))\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(m):\n",
    "        #         if mat[i][j]!=0: # mat[i][j]=0就不需要操作了\n",
    "        #             result[i][j]=bfs(i,j)\n",
    "        # return result\n",
    "\n",
    "\n",
    "        # 1）真正有效的bfs\n",
    "        # 但在实际的题目中，我们会有不止一个0。我们会想，要是我们可以把这些0 看成一个整体好了。有了这样的想法，我们可以添加一个「超级零」，它与矩阵中所有的0相连，这样的话，任意一个1到它最近的0的距离，会等于这个1到「超级零」的距离减去一。\n",
    "        # 由于我们只有一个「超级零」，我们就以它为起点进行广度优先搜索。这个「超级零」只和矩阵中的0相连，所以在广度优先搜索的第一步中，「超级零」会被弹出队列，而所有的0会被加入队列，它们到「超级零」的距离为1。\n",
    "        # 这就等价于：一开始我们就将所有的0加入队列，它们的初始距离为0。这样以来，在广度优先搜索的过程中，我们每遇到一个1，就得到了它到「超级零」的距离减去一，也就是 这个1到最近的0的距离。 \n",
    "        # m,n=len(mat),len(mat[0]) # [m,n]\n",
    "        # dist=[[0]*n for _ in range(m)]\n",
    "        # zeroes_pos=[(i,j) for i in range(m) for j in range(n) if mat[i][j]==0]\n",
    "        # # 将所有的0添加到初始队列中\n",
    "        # q=collections.deque(zeroes_pos)\n",
    "        # seen=set(zeroes_pos) # 找过的点不需要再找了\n",
    "        # # 广度优先搜索\n",
    "        # while q:\n",
    "        #     i,j=q.popleft()\n",
    "        #     for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "        #         if 0<=ni<m and 0<=nj<n and (ni,nj) not in seen:\n",
    "        #             dist[ni][nj]=dist[i][j]+1\n",
    "        #             q.append((ni,nj))\n",
    "        #             seen.add((ni,nj))\n",
    "        # return dist\n",
    "\n",
    "        # 动态规划！！！\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 初始化动态规划的数组，所有的距离值都设置为一个很大的数\n",
    "        dist = [[10**9] * n for _ in range(m)]\n",
    "        # 如果 (i, j) 的元素为 0，那么距离为 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dist[i][j] = 0\n",
    "        # 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)\n",
    "                if j - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)\n",
    "        # 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n):\n",
    "                if i + 1 < m:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)\n",
    "                if j - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)\n",
    "        # 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序\n",
    "        for i in range(m):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)\n",
    "                if j + 1 < n:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)\n",
    "        # 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i + 1 < m:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)\n",
    "                if j + 1 < n:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = [[inf] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0: ans[i][j] = 0\n",
    "                else:\n",
    "                    if i > 0 : ans[i][j] = min(ans[i][j], ans[i-1][j] + 1)\n",
    "                    if j > 0 : ans[i][j] = min(ans[i][j], ans[i][j-1] + 1)\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if mat[i][j] == 0: ans[i][j] = 0\n",
    "                else:\n",
    "                    if i < m-1: ans[i][j] = min(ans[i][j], ans[i+1][j] + 1)\n",
    "                    if j < n-1: ans[i][j] = min(ans[i][j], ans[i][j+1] + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[inf]*n for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0: dp[i][j]=0\n",
    "                else:\n",
    "                    if i==0 and j==0: continue\n",
    "                    elif i==0: dp[i][j] = min(dp[i][j], dp[i][j-1]+1)\n",
    "                    elif j==0: dp[i][j] = min(dp[i][j], dp[i-1][j]+1)\n",
    "                    else: dp[i][j] = min([dp[i][j], dp[i-1][j]+1, dp[i][j-1]+1])\n",
    "        \n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if mat[i][j]==0: dp[i][j]=0\n",
    "                else:\n",
    "                    if i==m-1 and j==n-1: continue\n",
    "                    elif i==m-1: dp[i][j] = min(dp[i][j], dp[i][j+1]+1)\n",
    "                    elif j==n-1: dp[i][j] = min(dp[i][j], dp[i+1][j]+1)\n",
    "                    else: dp[i][j] = min([dp[i][j], dp[i+1][j]+1, dp[i][j+1]+1])\n",
    "\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        nrow = len(mat)\n",
    "        ncol = len(mat[0])\n",
    "\n",
    "        def bfs(i, j):\n",
    "            q = deque()\n",
    "            visited = set()\n",
    "\n",
    "            q.append((i,j))\n",
    "            visited.add((i,j))\n",
    "\n",
    "            step = 0\n",
    "            while len(q)>0:\n",
    "                N = len(q)\n",
    "                for _ in range(N):\n",
    "                    ci, cj = q.popleft()\n",
    "                    if mat[ci][cj]==0:\n",
    "                        return step\n",
    "                    \n",
    "                    for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                        if ci+di<0 or ci+di>=nrow or cj+dj<0 or cj+dj>=ncol:\n",
    "                            continue\n",
    "                        if (ci+di,cj+dj) not in visited:\n",
    "                            q.append((ci+di,cj+dj))\n",
    "                            visited.add((ci+di,cj+dj))\n",
    "                step += 1\n",
    "        \n",
    "        ans = [[0 for _ in range(ncol)] for _ in range(nrow)]\n",
    "        for i in range(nrow):\n",
    "            for j in range(ncol):\n",
    "                ans[i][j] = bfs(i, j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        dp = [[float(\"inf\")] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]:\n",
    "                    dis = float(\"inf\")\n",
    "                    if i - 1 >= 0:\n",
    "                        dis = min(dis,dp[i - 1][j])\n",
    "                    if j - 1 >= 0:\n",
    "                        dis = min(dis,dp[i][j - 1])\n",
    "                    if i + 1 < m:\n",
    "                        dis = min(dis,dp[i + 1][j])\n",
    "                    if j + 1 < n:\n",
    "                        dis = min(dis,dp[i][j + 1])\n",
    "                    dp[i][j] = dis + 1\n",
    "                else:\n",
    "                    dp[i][j] = 0\n",
    "                    \n",
    "        \n",
    "        for i in range(m - 1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if mat[i][j]:\n",
    "                    dis = float(\"inf\")\n",
    "                    if i - 1 >= 0:\n",
    "                        dis = min(dis,dp[i - 1][j])\n",
    "                    if j - 1 >= 0:\n",
    "                        dis = min(dis,dp[i][j - 1])\n",
    "                    if i + 1 < m:\n",
    "                        dis = min(dis,dp[i + 1][j])\n",
    "                    if j + 1 < n:\n",
    "                        dis = min(dis,dp[i][j + 1])\n",
    "                    dp[i][j] = min(dis + 1,dp[i][j])\n",
    "                else:\n",
    "                    dp[i][j] = 0\n",
    "        # print(dp)\n",
    "        \n",
    "        return dp\n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        dp=[[float('inf')]*(n) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    dp[i][j]=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i>=1:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i-1][j]+1)\n",
    "                if j>=1:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i][j-1]+1)\n",
    "                  \n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if i<m-1:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i+1][j]+1)\n",
    "                if j<n-1:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i][j+1]+1)\n",
    "        for i in range(m):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if i>=1:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i-1][j]+1)\n",
    "                if j<n-1:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i][j+1]+1)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n):\n",
    "                if j>=1:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i][j-1]+1)\n",
    "                if i<m-1:\n",
    "                    dp[i][j]=min(dp[i][j],dp[i+1][j]+1)\n",
    "        return dp     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def update(self, ret, i, j, m, n):\n",
    "        if i > 0: ret[i][j] = min(ret[i][j], ret[i - 1][j] + 1)\n",
    "        if j > 0: ret[i][j] = min(ret[i][j], ret[i][j - 1] + 1)\n",
    "        if i < m - 1: ret[i][j] = min(ret[i][j], ret[i + 1][j] + 1)\n",
    "        if j < n - 1: ret[i][j] = min(ret[i][j], ret[i][j + 1] + 1)\n",
    "\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        ret = [[m * n] * n for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0: ret[i][j] = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.update(ret, i, j, m, n)\n",
    "\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n):\n",
    "                self.update(ret, i, j, m, n)\n",
    "\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                self.update(ret, i, j, m, n)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                self.update(ret, i, j, m, n)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        r, c = len(mat), len(mat[0])\n",
    "\n",
    "        dp = [[float('inf')] * c for _ in range(r)]\n",
    "\n",
    "        for i in range(len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                if i == j== 0:\n",
    "                    if mat[i][j] == 0:\n",
    "                        dp[i][j] = 0\n",
    "                    continue\n",
    "                if mat[i][j] == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j] if i - 1>= 0 else float('inf'), dp[i][j - 1] if j - 1 >= 0 else float('inf')) + 1\n",
    "\n",
    "        \n",
    "\n",
    "        for i in range(len(dp) - 1, -1, -1):\n",
    "            for j in range(len(dp[0]) - 1, -1, -1):\n",
    "                if i == r - 1 and j == c - 1:\n",
    "                    continue\n",
    "                \n",
    "                if i + 1 < r:\n",
    "                    dp[i][j] = min(dp[i][j],dp[i + 1][j] + 1)\n",
    "                \n",
    "                if j + 1 < c:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1)\n",
    "\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 初始化动态规划的数组，所有的距离值都设置为一个很大的数\n",
    "        dist = [[inf for _ in range(n)] for _ in range(m)]\n",
    "        # 如果 (i, j) 的元素为 0，那么距离为 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dist[i][j] = 0\n",
    "        # 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)\n",
    "                if j - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)\n",
    "        # 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n):\n",
    "                if i + 1 < m:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)\n",
    "                if j - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)\n",
    "        # 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序\n",
    "        for i in range(m):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)\n",
    "                if j + 1 < n:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)\n",
    "        # 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i + 1 < m:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)\n",
    "                if j + 1 < n:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        rows = len(mat)\n",
    "        cols = len(mat[0])\n",
    "        q = []\n",
    "        dists = [[0] * cols for _ in range(rows)] \n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append([i,j])\n",
    "                else:\n",
    "                    dists[i][j] = inf\n",
    "        dirs = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        while q:\n",
    "            pos = q.pop(0)\n",
    "            dist = dists[pos[0]][pos[1]]\n",
    "            for d in dirs:\n",
    "                r = pos[0] + d[0]\n",
    "                c = pos[1] + d[1]\n",
    "                if r >= 0 and c >= 0 and r < rows and c < cols:\n",
    "                    if dists[r][c] > dist + 1:\n",
    "                        dists[r][c] = dist + 1\n",
    "                        q.append([r,c])\n",
    "        return dists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = [[float('inf') for j in range(n)] for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    res[i][j] = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0:\n",
    "                    res[i][j] = min(res[i][j], res[i-1][j] + 1)\n",
    "                if j > 0:\n",
    "                    res[i][j] = min(res[i][j], res[i][j-1] + 1)\n",
    "        \n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if i < m - 1:\n",
    "                    res[i][j] = min(res[i][j], res[i+1][j] + 1)\n",
    "                if j < n - 1:\n",
    "                    res[i][j] = min(res[i][j], res[i][j+1] + 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "\n",
    "        dp = [[float(\"inf\") for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] != 0:\n",
    "                    if i != 0 and j != 0:\n",
    "                        dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1\n",
    "                    elif i == 0 and j != 0:\n",
    "                        dp[i][j] = dp[i][j-1] + 1\n",
    "                    elif i != 0 and j == 0:\n",
    "                        dp[i][j] = dp[i-1][j] + 1\n",
    "                    elif i == 0 and j == 0:\n",
    "                        continue\n",
    "                else:\n",
    "                    dp[i][j] = 0\n",
    "        for i in reversed(range(m)):\n",
    "            for j in reversed(range(n)):\n",
    "                if dp[i][j] != 0:\n",
    "                    # 分四类情况 i == m-1，i != m-1\n",
    "                    if i == m-1 and j == n-1:\n",
    "                        continue\n",
    "                    elif i != m-1 and j != n-1:\n",
    "                        dp[i][j] = min(min(dp[i][j+1], dp[i+1][j]) + 1, dp[i][j])\n",
    "                    elif i != m-1 and j == n-1:\n",
    "                        dp[i][j] = min(dp[i+1][j] + 1, dp[i][j])\n",
    "                    elif i == m-1 and j != n-1:\n",
    "                        dp[i][j] = min(dp[i][j+1] + 1, dp[i][j])\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    ans[i][j] = 0\n",
    "                    queue.append((i, j))\n",
    "        distance = 1\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                x, y = queue.popleft()\n",
    "                for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                    if 0 <= nx < m and 0 <= ny < n and ans[nx][ny] < 0:\n",
    "                        ans[nx][ny] = distance\n",
    "                        queue.append((nx, ny))\n",
    "            distance += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n,m = len(mat),len(mat[0])\n",
    "\n",
    "        dist = [[10**4]*m for _ in range(n)]\n",
    "\n",
    "        queue = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j]==0:\n",
    "                    dist[i][j]=0\n",
    "                    queue.append((i,j))\n",
    "\n",
    "        while queue:\n",
    "            cur_i,cur_j = queue.popleft()\n",
    "            for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                if dx + cur_i >=0 and dx + cur_i <n and dy + cur_j >=0 and dy + cur_j <m and  dist[dx + cur_i][dy + cur_j] > dist[cur_i][cur_j] + 1:\n",
    "                    dist[dx + cur_i][dy + cur_j] = dist[cur_i][cur_j] + 1\n",
    "                    queue.append((dx + cur_i, dy + cur_j))\n",
    "\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dq = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dq.append((i, j))\n",
    "                else:\n",
    "                    dp[i][j] = inf\n",
    "        while dq:\n",
    "            l = len(dq)\n",
    "            for _ in range(l):\n",
    "                mi, mj = dq.popleft()\n",
    "                for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                    ni, nj = mi - di, mj - dj\n",
    "                    if 0 <= ni < m and 0 <= nj < n and dp[ni][nj] > dp[mi][mj] + 1:\n",
    "                        dp[ni][nj] = dp[mi][mj] + 1\n",
    "                        dq.append((ni, nj))\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        rows = len(mat)\n",
    "        cols = len(mat[0])\n",
    "        q = deque()\n",
    "        dists = [[0] * cols for _ in range(rows)] \n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append([i,j])\n",
    "                else:\n",
    "                    dists[i][j] = inf\n",
    "        dirs = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        while q:\n",
    "            pos = q.popleft()\n",
    "            dist = dists[pos[0]][pos[1]]\n",
    "            for d in dirs:\n",
    "                r = pos[0] + d[0]\n",
    "                c = pos[1] + d[1]\n",
    "                if r >= 0 and c >= 0 and r < rows and c < cols:\n",
    "                    if dists[r][c] > dist + 1:\n",
    "                        dists[r][c] = dist + 1\n",
    "                        q.append([r,c])\n",
    "        return dists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(mat)\n",
    "        m=len(mat[0])\n",
    "        vst=[[False for _ in range(m)]for _ in range(n)]\n",
    "        queue=[]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append([i,j,0])\n",
    "                    vst[i][j]=True\n",
    "        while queue:\n",
    "            i,j,w=queue.pop(0)\n",
    "            for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if x>=0 and x<n and y>=0 and y<m and not vst[x][y] and mat[x][y]==1:\n",
    "                    vst[x][y]=True\n",
    "                    mat[x][y]=w+1\n",
    "                    queue.append([x,y,mat[x][y]])\n",
    "        return mat\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        q = collections.deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append([i,j,0])\n",
    "        dirs = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        while q:\n",
    "            x,y,dis = q.popleft() \n",
    "            for dx,dy in dirs:\n",
    "                if 0<=dx+x<m and 0<=y+dy<n and mat[x+dx][y+dy]==1:\n",
    "                    q.append([x+dx,y+dy,dis+1])\n",
    "                    mat[x+dx][y+dy] = 0\n",
    "                    res[x+dx][y+dy] = dis+1\n",
    "        \n",
    "\n",
    "        \n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        dp_list = [[20001] * n for i in range(m)]\n",
    "        used = [[0] * n for i in range(m)]\n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dp_list[i][j] = 0\n",
    "                    used[i][j] = 1\n",
    "                    count += 1\n",
    "        flag = 0\n",
    "        while count < m * n:\n",
    "            flag += 1\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if used[i][j] == 0:\n",
    "                        for dx,dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                            curx = i + dx\n",
    "                            cury = j + dy\n",
    "                            if curx >=0 and cury >= 0 and curx < m and cury < n:\n",
    "                                dp_list[i][j] = min(dp_list[i][j], dp_list[curx][cury] + 1)\n",
    "                        if dp_list[i][j] == flag:\n",
    "                            count += 1\n",
    "                            used[i][j] = 1\n",
    "        return dp_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        ans = [[0]*m for _ in range(n)]\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append((i, j))\n",
    "        movement = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        count = 1\n",
    "        while q:\n",
    "            nxt = []\n",
    "            for i, j in q:\n",
    "                for x, y in movement:\n",
    "                    xx, yy = i+x, j+y\n",
    "                    if 0<=xx<n and 0<=yy< m and mat[xx][yy] and not ans[xx][yy]:\n",
    "                        nxt.append([xx,yy])\n",
    "                        ans[xx][yy] = count\n",
    "            q=nxt\n",
    "            count += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat) :\n",
    "        res=[[-1 for i in range(len(mat[0]))] for j in range(len(mat))]\n",
    "        lis1 = deque()\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[i])):\n",
    "                if mat[i][j]==0:\n",
    "                    lis1.append((i,j))\n",
    "                    res[i][j]=0\n",
    "        num=1\n",
    "        lis2=deque()\n",
    "        while len(lis1)!=0 or len(lis2)!=0:\n",
    "            if len(lis1)==0:\n",
    "                lis1=lis2.copy()\n",
    "                lis2.clear()\n",
    "                num+=1\n",
    "            i,j=lis1.popleft()\n",
    "            if i-1>=0 and res[i-1][j]==-1:\n",
    "                res[i-1][j]=num\n",
    "                lis2.append((i-1,j))\n",
    "            if j - 1 >= 0 and res[i ][j-1] == -1:\n",
    "                res[i][j-1] = num\n",
    "                lis2.append((i, j-1))\n",
    "            if i + 1 < len(mat) and res[i+1][j] == -1:\n",
    "                res[i + 1][j] = num\n",
    "                lis2.append((i + 1, j))\n",
    "            if j + 1 < len(mat[0]) and res[i][j + 1] == -1:\n",
    "                res[i][j + 1] = num\n",
    "                lis2.append((i, j + 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        dists = [[0]*n for _ in range(m)]\n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append((i,j))\n",
    "                    dists[i][j] = 0\n",
    "                else:\n",
    "                    dists[i][j] = float('inf')\n",
    "        \n",
    "        dirs = [(-1,0),(1,0),(0,1),(0,-1)]\n",
    "        while q:\n",
    "            pos = q.popleft()\n",
    "            for d in dirs:\n",
    "                row,col = pos[0] + d[0],pos[1] + d[1]\n",
    "                if row < 0 or row >= m or col < 0 or col >= n:\n",
    "                    continue\n",
    "                else:\n",
    "                    if dists[pos[0]][pos[1]] + 1 >= dists[row][col]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        dists[row][col] = dists[pos[0]][pos[1]] + 1\n",
    "                        q.append((row,col))\n",
    "        return dists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        #深度优先是不对的，会出问题，这道题要用广度优先。\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        MAX_INT = int(1e9)\n",
    "        # 初始化距离矩阵，1的地方初始化为一个很大的数，0的地方初始化为0\n",
    "        dist = [[MAX_INT if mat[i][j] == 1 else 0 for j in range(n)] for i in range(m)]\n",
    "        # 方向数组\n",
    "        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        # 初始化队列，将所有0的位置入队\n",
    "        q = deque([(i, j) for i in range(m) for j in range(n) if mat[i][j] == 0])\n",
    "\n",
    "        def BFS():\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for dx, dy in directions:\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if x >= 0 and x < m and y >= 0 and y < n and dist[x][y] > dist[i][j] + 1:\n",
    "                        dist[x][y] = dist[i][j] + 1\n",
    "                        q.append((x, y))\n",
    "\n",
    "        BFS()\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        q = []\n",
    "        dis = [[inf] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dis[i][j] = 0\n",
    "                    q.append((i,j))\n",
    "        while q:\n",
    "            nq = []\n",
    "            for x, y in q:\n",
    "                for nx, ny in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):\n",
    "                    if not (0<=nx<m and 0<=ny<n): continue\n",
    "                    if mat[nx][ny] == 0: continue\n",
    "                    if dis[nx][ny] > dis[x][y] + 1:\n",
    "                        dis[nx][ny] = dis[x][y] + 1\n",
    "                        nq.append((nx,ny))\n",
    "            q = nq\n",
    "        return dis\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dist = [[0] * n for _ in range(m)]\n",
    "        zeroes_pos = [(i, j) for i in range(m) for j in range(n) if mat[i][j] == 0]\n",
    "        # 将所有的 0 添加进初始队列中\n",
    "        q = collections.deque(zeroes_pos)\n",
    "        seen = set(zeroes_pos)\n",
    "\n",
    "        # 广度优先搜索\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen:\n",
    "                    dist[ni][nj] = dist[i][j] + 1\n",
    "                    q.append((ni, nj))\n",
    "                    seen.add((ni, nj))\n",
    "        \n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        dis = [[0]*n for _ in range(m)]\n",
    "        stack = []\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if not mat[x][y]:\n",
    "                    stack.append([x,y])\n",
    "        step = 1\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for x,y in stack:\n",
    "                for a,b in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                    if 0 <= a < m and 0 <= b < n and mat[a][b] != 0:\n",
    "                        mat[a][b] = 0\n",
    "                        dis[a][b] = step\n",
    "                        nex.append([a,b])\n",
    "            stack = nex\n",
    "            step += 1\n",
    "        return dis \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        # BFS\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        Dir = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        # def dfs(x,y):\n",
    "        #     cnt = 1\n",
    "        #     queue = [(x,y)]\n",
    "        #     while queue:\n",
    "        #         size = len(queue)\n",
    "        #         for _ in range(size):\n",
    "        #             x,y = queue.pop(0)\n",
    "        #             for a,b in Dir:\n",
    "        #                 newx = x+a\n",
    "        #                 newy = y+b \n",
    "        #                 if 0<= newx<m and 0<= newy<n:\n",
    "        #                     if mat[newx][newy] == 0:\n",
    "        #                         return cnt\n",
    "        #                     else:\n",
    "        #                         queue.append((newx,newy))\n",
    "        #         cnt += 1\n",
    "        # grid = [[0]*n for _ in range(m)]\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "        queue = collections.deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    visited[i][j] = 1\n",
    "                    queue.append((i,j))\n",
    "        cnt = 1\n",
    "        while queue:\n",
    "           \n",
    "            size = len(queue)\n",
    "            print(queue)\n",
    "            for _ in range(size):\n",
    "                x,y = queue.popleft()\n",
    "                for a,b in Dir:\n",
    "                    newx = a+x\n",
    "                    newy = b+y\n",
    "                    if 0<= newx<m and 0<= newy<n and not visited[newx][newy] and mat[newx][newy] == 1:\n",
    "                        # print(cnt)\n",
    "                        mat[newx][newy] = cnt\n",
    "                        visited[newx][newy] = 1\n",
    "                        queue.append((newx,newy))\n",
    "            cnt += 1\n",
    "        return mat\n",
    "\n",
    "        # return grid\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        zeros = set()\n",
    "        ans = []\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if mat[r][c] == 0:\n",
    "                    zeros.add((r, c))\n",
    "                else:\n",
    "                    mat[r][c] = -1\n",
    "        d = zeros\n",
    "        step = 1\n",
    "        while d:\n",
    "            nex = []\n",
    "            for x, y in d:\n",
    "                for dx, dy in dirs:\n",
    "                    cx, cy = x+dx, y+dy\n",
    "                    if cx<0 or cx>=m or cy<0 or cy>=n:\n",
    "                        continue\n",
    "                    if mat[cx][cy] == -1:\n",
    "                        mat[cx][cy] = step\n",
    "                        nex.append((cx, cy))\n",
    "            d = nex\n",
    "            step += 1\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n,m = len(mat), len(mat[0])\n",
    "        moves = [[0, 1], [1, 0], [-1, 0], [0, -1]]\n",
    "        queue = []\n",
    "        dp = [[float(\"inf\")]*m for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j]==0:\n",
    "                    dp[i][j]=0\n",
    "                    queue.append((i, j))\n",
    "\n",
    "        while queue:\n",
    "            pos = queue.pop(0)\n",
    "            for move in moves:\n",
    "                row, col = pos[0] + move[0], pos[1] + move[1]\n",
    "                if row >=0 and row <n and col>=0 and col<m:\n",
    "                    if dp[row][col] > dp[pos[0]][pos[1]] + 1:\n",
    "                        dp[row][col] =  dp[pos[0]][pos[1]] + 1\n",
    "                        queue.append((row, col))\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n,m = len(mat), len(mat[0])\n",
    "        moves = [[0, 1], [1, 0], [-1, 0], [0, -1]]\n",
    "        queue = []\n",
    "        dp = [[float(\"inf\")]*m for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j]==0:\n",
    "                    dp[i][j]=0\n",
    "                    queue.append((i, j))\n",
    "\n",
    "        while queue:\n",
    "            pos = queue.pop(0)\n",
    "            for move in moves:\n",
    "                row, col = pos[0] + move[0], pos[1] + move[1]\n",
    "                if row >=0 and row <n and col>=0 and col<m:\n",
    "                    if dp[row][col] > dp[pos[0]][pos[1]] + 1:\n",
    "                        dp[row][col] =  dp[pos[0]][pos[1]] + 1\n",
    "                        queue.append((row, col))\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        # res = [[0]*len(mat[0]) for _ in range(len(mat))]\n",
    "        # m,n = len(mat),len(mat[0])\n",
    "        # dirs = [[0,1],[1,0],[-1,0],[0,-1]]\n",
    "\n",
    "        # def bfs(a,b):\n",
    "        #     q = [[a,b,0]]\n",
    "        #     visited = [[False]*n for _ in range(m)]\n",
    "        #     while q:\n",
    "        #         x,y,p = q.pop(0)\n",
    "        #         visited[x][y] = True\n",
    "        #         if mat[x][y]==0:\n",
    "        #             return p\n",
    "        #         for dir in dirs:\n",
    "        #             nx = x+dir[0]\n",
    "        #             ny = y+dir[1]\n",
    "        #             if nx<0 or nx>m-1 or ny<0 or ny>n-1 or visited[nx][ny]:\n",
    "        #                 continue\n",
    "        #             q.append([nx,ny,p+1])\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if mat[i][j]==0:\n",
    "        #             res[i][j] = 0\n",
    "        #         else:\n",
    "        #             res[i][j] = bfs(i,j)\n",
    "        # return res\n",
    "\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        dist = [[0]*n for _ in range(m)]\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "        dirs = [[0,1],[1,0],[-1,0],[0,-1]]\n",
    "\n",
    "        q = [[i,j] for i in range(m) for j in range(n) if mat[i][j] == 0]\n",
    "\n",
    "        while q:\n",
    "            x,y = q.pop(0)\n",
    "            # visited[x][y] = True\n",
    "            for dir in dirs:\n",
    "                nx = x+dir[0]\n",
    "                ny = y+dir[1]\n",
    "                if nx<0 or nx>m-1 or ny<0 or ny>n-1 or visited[nx][ny] or mat[nx][ny]==0:\n",
    "                    continue\n",
    "                q.append([nx,ny])\n",
    "                dist[nx][ny] = dist[x][y]+1\n",
    "                visited[nx][ny] = True\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef updateMatrix(self, mat):\n",
    "\t\tm = len(mat)\n",
    "\t\tn = len(mat[0])\n",
    "\t\tans = [[-1] * n for _ in range(m)]\n",
    "\t\tpool = deque()\n",
    "\t\tfor i in range(m):\n",
    "\t\t\tfor j in range(n):\n",
    "\t\t\t\tif mat[i][j] == 0:\n",
    "\t\t\t\t\tpool.append([0, i, j])\n",
    "\t\t\t\t\tans[i][j] = 0\n",
    "\t\twhile pool:\n",
    "\t\t\td, x, y = pool.popleft()\n",
    "\t\t\tfor dx, dy in [[1,0], [0,1], [-1,0], [0,-1]]:\n",
    "\t\t\t\tx1 = x + dx\n",
    "\t\t\t\ty1 = y + dy\n",
    "\t\t\t\tif 0 <= x1 < m and 0 <= y1 < n and ans[x1][y1] == -1:\n",
    "\t\t\t\t\tans[x1][y1] = d + 1\n",
    "\t\t\t\t\tpool.append([d + 1, x1, y1])\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        result=[[0]*n for _ in range(m)]\n",
    "        visited=[[0]*n for _ in range(m)]\n",
    "\n",
    "        queue=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append((i,j))\n",
    "                    visited[i][j]=1\n",
    "\n",
    "        direction=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        step=0\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "\n",
    "            for index in range(size):\n",
    "                y,x=queue.pop(0)\n",
    "                if mat[y][x]==1:\n",
    "                    result[y][x]=step\n",
    "\n",
    "                for dx,dy in direction:\n",
    "                    newx,newy=x+dx,y+dy\n",
    "                    if newx<0 or newx>=n or newy<0 or newy>=m or visited[newy][newx]==1:\n",
    "                        continue\n",
    "                    queue.append((newy,newx))\n",
    "                    visited[newy][newx]=1\n",
    "                \n",
    "            step+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        visited = [[False] * m for _ in range(n)]\n",
    "        res = [[0] * m for _ in range(n)]\n",
    "        queue = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j] == 0:\n",
    "                    res[i][j] == 1\n",
    "                    visited[i][j] = True\n",
    "                    queue.append((i, j))\n",
    "        step = 1\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                i, j = queue.popleft()\n",
    "                for k, l in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                    if 0 <= k < n and 0 <= l < m and visited[k][l] == False:\n",
    "                        res[k][l] = step\n",
    "                        visited[k][l] = True\n",
    "                        queue.append((k, l))\n",
    "            step += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        result=[[0]*n for _ in range(m)]\n",
    "        visited=[[0]*n for _ in range(m)]\n",
    "\n",
    "        queue=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append((i,j))\n",
    "                    visited[i][j]=1\n",
    "        \n",
    "\n",
    "        direction=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        step=0\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "\n",
    "            for index in range(size):\n",
    "                y,x=queue.pop(0)\n",
    "\n",
    "                if mat[y][x]==1:\n",
    "                    result[y][x]=step\n",
    "\n",
    "                for dx,dy in direction:\n",
    "                    newx,newy=x+dx,y+dy\n",
    "\n",
    "                    if newx<0 or newx>=n or newy<0 or newy>=m or visited[newy][newx]==1:\n",
    "                        continue\n",
    "                    queue.append((newy,newx))\n",
    "                    visited[newy][newx]=1\n",
    "                \n",
    "            step+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        self.resmatrix = [[9999999]*n for i in range(m)]\n",
    "        self.visited = [[0]*n for i in range(m)]\n",
    "\n",
    "\n",
    "        queue = []\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append([i,j])\n",
    "                    self.resmatrix[i][j]=0\n",
    "\n",
    "        while queue:\n",
    "            i,j = queue.pop(0)\n",
    "            for ia,ja in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                x=i+ia\n",
    "                y=ja+j \n",
    "                if 0<=x<m and 0<=y<n and self.resmatrix[i][j]+1<self.resmatrix[x][y]:\n",
    "                    self.resmatrix[x][y] = self.resmatrix[i][j]+1\n",
    "                    queue.append([x,y])\n",
    "                \n",
    "        return self.resmatrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "\n",
    "        queue = []\n",
    "        visited = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    queue.append([i, j])\n",
    "                    visited[(i,j)] = 1\n",
    "        \n",
    "        step = 1\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                i, j = queue.pop(0)\n",
    "                visited[(i,j)] = 1\n",
    "                for di, dj in [(-1,0), (1,0), (0,-1), (0, 1)]:\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    if 0 <= new_i < m and 0 <= new_j < n and (new_i, new_j) not in visited:\n",
    "                        queue.append([new_i, new_j])\n",
    "                        ans[new_i][new_j] = ans[i][j] + 1\n",
    "                        visited[(new_i, new_j)] = 1\n",
    "            step += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        column = len(mat[0])\n",
    "\n",
    "        visted=[[False]*column for _ in range(row)]\n",
    "\n",
    "        result=[[float('inf')]*column for _ in range(row)]\n",
    "\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(column):\n",
    "                if mat[i][j]==0:\n",
    "                    visted[i][j]=True\n",
    "                    result[i][j]=0\n",
    "                    queue.append((i,j))\n",
    "        step=1\n",
    "        while queue:\n",
    "            length=len(queue)\n",
    "            for _ in range(length):\n",
    "                r, l=queue.popleft()\n",
    "                for i, j in ((r-1,l),(r+1,l),(r,l-1),(r,l+1)):\n",
    "                    if 0 <= i < row and 0 <= j < column and visted[i][j] == False:\n",
    "                        result[i][j]=step\n",
    "                        visted[i][j]=True\n",
    "                        queue.append((i,j))\n",
    "            step+=1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "            题目分析：\n",
    "                改题可分为3种情况\n",
    "                1. 如果该位置是0，则为不变。\n",
    "                2. 如果该位置的四周(上下左右)存在0，则该位置置1.\n",
    "                3. 如果该位置被1包裹，则查询4周的1到0的距离，该位置的值则为4周离0最近的距离+1\n",
    "            \n",
    "            题目做法：\n",
    "                1. 广度优先遍历(bfs)\n",
    "                    1.1 创建一个新的二维数组dists，用于存放每一个位置离0的距离\n",
    "                    1.2 记录值为0的位置，并把该位置放进广度优先队列queue，同时，在dists上，把值为0的位置的值置0，值为1的位置置为无穷大\n",
    "                    1.3 对于队列里的每一个元素(一开始都是0所处的位置)，把每一个元素的4个方向与0的距离都算出来（如果某个位置的值也为0，则不进行任何操作，如果为1，则dists该位置的距离为1，并把该位置添加进队列里）\n",
    "                    1.4 重复1.3的操作，以0为起点一直走，直到队列里面没有元素，所有的位置都走完了\n",
    "        \"\"\"\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 初始化\n",
    "        dists = [[[0] for i in range(n)] for j in range(m)]\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "                    dists[i][j] = 0\n",
    "                else:\n",
    "                    dists[i][j] = float('inf')\n",
    "        \n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上/下/左/右\n",
    "        while queue:\n",
    "            pos = queue.pop(0) # 拿出队头\n",
    "            for d in dirs:\n",
    "                row, col = pos[0] + d[0], pos[1] + d[1]\n",
    "                if row < 0 or row >=m or col <0 or col >= n: continue\n",
    "                else:\n",
    "                    if dists[pos[0]][pos[1]] + 1 >= dists[row][col]: continue\n",
    "                    else: \n",
    "                        dists[row][col] = dists[pos[0]][pos[1]] + 1\n",
    "                        queue.append((row, col))\n",
    "        \n",
    "        return dists\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        dq = deque()\n",
    "\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "\n",
    "        ret = [[float('inf') for i in range(n)] for j in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dq.append(\n",
    "                        (i, j, 0)\n",
    "                    )\n",
    "                    ret[i][j] = 0\n",
    "\n",
    "        dirs = [(0, -1), (-1, 0), (1, 0), (0, 1)]\n",
    "        while dq:\n",
    "            y, x, dep = dq.popleft()\n",
    "\n",
    "            for d in dirs:\n",
    "                dy, dx = y + d[0], x + d[1]\n",
    "                if m > dy >=0 and n > dx >= 0:\n",
    "                    if dep + 1 < ret[dy][dx]:\n",
    "                        ret[dy][dx] = dep + 1\n",
    "                        dq.append((dy, dx, dep + 1))\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        column = len(mat[0])\n",
    "        # 是否被访问过\n",
    "        visted = [[False] * column for _ in range(row)]\n",
    "        # 最短距离结果\n",
    "        result = [[10 ** 5] * column for _ in range(row)]\n",
    "        # 初始化\n",
    "        queue = collections.deque()\n",
    "        for i in range(row):\n",
    "            for j in range(column):\n",
    "                if mat[i][j] == 0:\n",
    "                    visted[i][j] = True\n",
    "                    result[i][j] = 0\n",
    "                    queue.append((i, j))\n",
    "\n",
    "        # 距离0点的距离 ， 每结束一个层级都要 +1\n",
    "        step = 1\n",
    "        # 队列进行层序遍历\n",
    "        while queue:\n",
    "            queue_lenth = len(queue)\n",
    "            # 同一层级的个数\n",
    "            for _ in range(queue_lenth):\n",
    "                # 元组可以直接这样赋值\n",
    "                r, l = queue.popleft()\n",
    "                \n",
    "                # 遍历上下左右 元组赋值的特性\n",
    "                for i, j in ((r - 1, l), (r + 1, l), (r, l - 1), (r, l + 1)):\n",
    "                    # 符合边界条件 且未被访问过的1点\n",
    "                    if 0 <= i < row and 0 <= j < column and visted[i][j] == False:\n",
    "                        result[i][j] = step\n",
    "                        visted[i][j] = True\n",
    "                        # 该点需要入队列\n",
    "                        queue.append((i, j))\n",
    "            \n",
    "            # 一个层级遍历结束 step需要 + 1\n",
    "            step += 1\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "            题目分析：\n",
    "                改题可分为3种情况\n",
    "                1. 如果该位置是0，则为不变。\n",
    "                2. 如果该位置的四周(上下左右)存在0，则该位置置1.\n",
    "                3. 如果该位置被1包裹，则查询4周的1到0的距离，该位置的值则为4周离0最近的距离+1\n",
    "            \n",
    "            题目做法：\n",
    "                1. 广度优先遍历(bfs)\n",
    "                    1.1 创建一个新的二维数组dists，用于存放每一个位置离0的距离\n",
    "                    1.2 记录值为0的位置，并把该位置放进广度优先队列queue，同时，在dists上，把值为0的位置的值置0，值为1的位置置为无穷大\n",
    "                    1.3 对于队列里的每一个元素(一开始都是0所处的位置)，把每一个元素的4个方向与0的距离都算出来（如果某个位置的值也为0，则不进行任何操作，如果为1，则dists该位置的距离为1，并把该位置添加进队列里）\n",
    "                    1.4 重复1.3的操作，以0为起点一直走，直到队列里面没有元素，所有的位置都走完了\n",
    "        \"\"\"\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 初始化\n",
    "        dists = [[[0] for i in range(n)] for j in range(m)]\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "                    dists[i][j] = 0\n",
    "                else:\n",
    "                    dists[i][j] = float('inf')\n",
    "        \n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上/下/左/右\n",
    "        while queue:\n",
    "            pos = queue.pop(0) # 拿出队头\n",
    "            for d in dirs:\n",
    "                row, col = pos[0] + d[0], pos[1] + d[1]\n",
    "                if row < 0 or row >=m or col <0 or col >= n: continue\n",
    "                else:\n",
    "                    if dists[pos[0]][pos[1]] + 1 >= dists[row][col]: continue\n",
    "                    else: \n",
    "                        dists[row][col] = dists[pos[0]][pos[1]] + 1\n",
    "                        queue.append((row, col))\n",
    "        \n",
    "        return dists\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        # 创建一个数组用来保存最后所有的结果，并初始化为最大整数，mat中为0的初始为0，并将0的坐标放入队列中\n",
    "        row,col=len(mat),len(mat[0])\n",
    "        result=[[0 for _ in range(col)] for _ in range(row)]\n",
    "        # print(result)\n",
    "        point=collections.deque()\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if mat[i][j]==0:\n",
    "                    # print(i,j)\n",
    "                    result[i][j]=0\n",
    "                    point.append((i,j))\n",
    "                else:\n",
    "                    result[i][j]=float('inf')\n",
    "        \n",
    "        # 广度优先遍历，如果当前节点的位置的上下左右到当前节点的距离大于最近 源节点+1 更新当前距离值并将该点加入队列中\n",
    "        dirs=[(-1,0),(1,0),(0,-1),(0,1)]\n",
    "        while point:\n",
    "            cur=point.popleft()\n",
    "            for i in range(4):\n",
    "                newrow,newcol=cur[0]+dirs[i][0],cur[1]+dirs[i][1]\n",
    "                if newrow<0 or newrow>=row or newcol<0 or newcol>=col:\n",
    "                    continue\n",
    "                if result[cur[0]][cur[1]]+1 > result[newrow][newcol]:\n",
    "                    continue\n",
    "                else:\n",
    "                    result[newrow][newcol]=result[cur[0]][cur[1]]+1\n",
    "                    point.append((newrow,newcol))\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        #深度优先是不对的，会出问题，这道题要用广度优先。\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        MAX_INT = int(1e9)\n",
    "        # 初始化距离矩阵，1的地方初始化为一个很大的数，0的地方初始化为0\n",
    "        dist = [[MAX_INT if mat[i][j] == 1 else 0 for j in range(n)] for i in range(m)]\n",
    "        # 方向数组\n",
    "        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        # 初始化队列，将所有0的位置入队\n",
    "        q = deque([(i, j) for i in range(m) for j in range(n)])\n",
    "        def BFS():\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for dx, dy in directions:\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if x >= 0 and x < m and y >= 0 and y < n and dist[x][y] > dist[i][j] + 1:\n",
    "                        dist[x][y] = dist[i][j] + 1\n",
    "                        q.append((x, y))\n",
    "        BFS()\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        q=queue.Queue()\n",
    "        dist=[[0 for i in range(n)] for j in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    q.put((i,j))\n",
    "        dx=[1,0,-1,0]\n",
    "        dy=[0,-1,0,1]\n",
    "        st=[[0 for i in range(n)] for j in range(m)]\n",
    "        while not q.empty():\n",
    "            x,y=q.get()\n",
    "            for i in range(4):\n",
    "                a=x+dx[i]\n",
    "                b=y+dy[i]\n",
    "                if a<0 or a>=m or b<0 or b>=n or st[a][b]==1 or mat[a][b]==0:\n",
    "                    continue\n",
    "                dist[a][b]=dist[x][y]+1\n",
    "                st[a][b]=1\n",
    "                q.put((a,b))\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        edge = set()\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    edge.add((i, j))\n",
    "                else:\n",
    "                    res.add((i, j))\n",
    "        \n",
    "        dis = [-1, 0, 1, 0, -1]\n",
    "        r = 1\n",
    "        while res:\n",
    "            new = set()\n",
    "            for i, j in edge:\n",
    "                for k in range(4):\n",
    "                    x = i + dis[k]\n",
    "                    y = j + dis[k+1]\n",
    "                    if (x, y) in res:\n",
    "                        new.add((x, y))\n",
    "                        mat[x][y] = r\n",
    "            res -= new\n",
    "            edge = new\n",
    "            r += 1\n",
    "        \n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        vis = set()\n",
    "        deque = collections.deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    vis.add((i, j))\n",
    "                    deque.append((i, j))\n",
    "\n",
    "        while deque:\n",
    "            i, j = deque.popleft()\n",
    "            for ni, nj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis:\n",
    "                    res[ni][nj] = res[i][j] + 1\n",
    "                    deque.append((ni, nj))\n",
    "                    vis.add((ni, nj))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat):\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        distance = [[0] * n for _ in range(m)]\n",
    "        queue = [(i, j) for i in range(m) for j in range(n) if mat[i][j] == 0]\n",
    "        recode = set(queue)\n",
    "\n",
    "        while queue:\n",
    "            i, j = queue.pop(0)\n",
    "            for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in recode:\n",
    "                    distance[x][y] = distance[i][j] + 1\n",
    "                    queue.append((x, y))\n",
    "                    recode.add((x, y))\n",
    "        return distance\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        zero_pos = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    zero_pos.append((i, j))\n",
    "        q = collections.deque(zero_pos)\n",
    "        seen = set(zero_pos)\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\n",
    "                newi, newj = i+di, j+dj\n",
    "                if 0<=newi<m and 0<=newj<n and (newi, newj) not in seen:\n",
    "                    res[newi][newj] = res[i][j] + 1\n",
    "                    q.append((newi, newj))\n",
    "                    seen.add((newi, newj))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        dist=[[0 for i in range(n)] for j in range(m)]\n",
    "        zeroes_pos=[(i,j) for i in range(m) for j in range(n) if mat[i][j]==0]\n",
    "        dx=[1,0,-1,0]\n",
    "        dy=[0,-1,0,1]\n",
    "        st=set(zeroes_pos)\n",
    "        q=collections.deque(zeroes_pos)\n",
    "        while q:\n",
    "            x,y=q.popleft()\n",
    "            for i in range(4):\n",
    "                a=x+dx[i]\n",
    "                b=y+dy[i]\n",
    "                if a<0 or a>=m or b<0 or b>=n or (a,b) in st:\n",
    "                    continue\n",
    "                dist[a][b]=dist[x][y]+1\n",
    "                st.add((a,b))\n",
    "                q.append((a,b))\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        res = [[0]*m for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(m):\n",
    "        #         if mat[i][j] == 0:\n",
    "        #             res[i][j] = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(m):\n",
    "        #         if i > 0:\n",
    "        #             res[i][j] = min(res[i-1][j]+1, res[i][j])\n",
    "        #         if j > 0:\n",
    "        #             res[i][j] = min(res[i][j-1]+1, res[i][j])\n",
    "        # for i in range(n-1, -1, -1):\n",
    "        #     for j in range(m-1, -1, -1):\n",
    "        #         if i < n-1:\n",
    "        #             res[i][j] = min(res[i+1][j]+1, res[i][j])\n",
    "        #         if j < m-1:\n",
    "        #             res[i][j] = min(res[i][j+1]+1, res[i][j])\n",
    "        # return res\n",
    "        q = deque()\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append((i,j,0))\n",
    "                    visited.add((i,j))\n",
    "        while q:\n",
    "            x, y, d = q.popleft()\n",
    "            res[x][y] = d\n",
    "            if x-1>=0 and (x-1, y) not in visited:\n",
    "                q.append((x-1, y, d+1))\n",
    "                visited.add((x-1, y))\n",
    "            if x+1<n and (x+1, y) not in visited:\n",
    "                q.append((x+1, y, d+1))\n",
    "                visited.add((x+1, y))\n",
    "            if y-1>=0 and (x, y-1) not in visited:\n",
    "                q.append((x, y-1, d+1))\n",
    "                visited.add((x, y-1))\n",
    "            if y+1<m and (x, y+1) not in visited:\n",
    "                q.append((x, y+1, d+1))\n",
    "                visited.add((x, y+1))\n",
    "        return res\n",
    "          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        dp=[[0 for i in range(n)] for j in range(m)]\n",
    "        rds=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        st=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(mat[i][j]==0):\n",
    "                    for x,y in rds:\n",
    "                        ni,nj=i+x,j+y\n",
    "                        if 0<=ni<m and 0<=nj<n and mat[ni][nj]==1:\n",
    "                            mat[ni][nj]=-1\n",
    "                            dp[ni][nj]=1\n",
    "                            st.add((ni,nj))\n",
    "        t=2\n",
    "        print(dp)\n",
    "        print(st)\n",
    "        while(st):\n",
    "            nst=set()\n",
    "            for i,j in st:\n",
    "                for x,y in rds:\n",
    "                    ni,nj=i+x,j+y\n",
    "                    if 0<=ni<m and 0<=nj<n and mat[ni][nj]==1:\n",
    "                        mat[ni][nj]=-1\n",
    "                        dp[ni][nj]=t\n",
    "                        nst.add((ni,nj))\n",
    "            t+=1\n",
    "            st=nst\n",
    "        return dp\n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        # bfs\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        d = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        cur = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    d[i][j] = 0\n",
    "\n",
    "                    cur.append((i,j))\n",
    "\n",
    "        # print(cur)\n",
    "        DIRS = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "        step = 0\n",
    "        while cur:\n",
    "            next = set()\n",
    "            step += 1\n",
    "            for i, j in cur:\n",
    "                for di, dj in DIRS:\n",
    "\n",
    "                    ni = i + di\n",
    "                    nj = j + dj\n",
    "\n",
    "                    if 0 <= ni < m and 0 <= nj < n and d[ni][nj] == -1:\n",
    "                        d[ni][nj] = step\n",
    "                        next.add((ni, nj))\n",
    "            \n",
    "            cur = next\n",
    "        \n",
    "        return d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        dist=[[0 for i in range(n)] for j in range(m)]\n",
    "        zeroes_pos=[(i,j) for i in range(m) for j in range(n) if mat[i][j]==0]\n",
    "        dx=[1,0,-1,0]\n",
    "        dy=[0,-1,0,1]\n",
    "        st=[[0 for i in range(n)] for j in range(m)]\n",
    "        q=collections.deque(zeroes_pos)\n",
    "        while q:\n",
    "            x,y=q.popleft()\n",
    "            for i in range(4):\n",
    "                a=x+dx[i]\n",
    "                b=y+dy[i]\n",
    "                if a<0 or a>=m or b<0 or b>=n or st[a][b]==1 or mat[a][b]==0:\n",
    "                    continue\n",
    "                dist[a][b]=dist[x][y]+1\n",
    "                st[a][b]=1\n",
    "                q.append((a,b))\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        zero_pos = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    zero_pos.append((i, j))\n",
    "        q = collections.deque(zero_pos)\n",
    "        seen = set(zero_pos)\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                newi, newj = i+di, j+dj\n",
    "                if 0<=newi<m and 0<=newj<n and (newi, newj) not in seen:\n",
    "                    res[newi][newj] = res[i][j] + 1\n",
    "                    q.append((newi, newj))\n",
    "                    seen.add((newi, newj))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        if not mat:\n",
    "            return mat\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        distance = [[0] * n for _ in range(m)]\n",
    "        queue = [(i,j) for i in range(m) for j in range(n) if mat[i][j] == 0]\n",
    "\n",
    "        recode = set(queue)\n",
    "\n",
    "        while queue:\n",
    "            i,j = queue.pop(0)\n",
    "            for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if 0<=x<m and 0<=y<n and (x,y) not in recode:\n",
    "                    distance[x][y] = distance[i][j] + 1\n",
    "                    queue.append((x,y))\n",
    "                    recode.add((x,y))\n",
    "        return distance\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0]*len(mat[0]) for _ in range(len(mat))]\n",
    "        visited = [[0]*len(mat[0]) for _ in range(len(mat))]\n",
    "        queue = []\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append(([i,j], 0))\n",
    "                    visited[i][j]=1\n",
    "        \n",
    "        dire = [[-1,0], [1,0], [0,-1], [0,1]]\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                pos, step = queue.pop(0)\n",
    "                if mat[pos[0]][pos[1]]==1:\n",
    "                        res[pos[0]][pos[1]]=step\n",
    "                for d in dire:\n",
    "                    newx = pos[0]+d[0]\n",
    "                    newy = pos[1]+d[1]\n",
    "                    if not 0<=newx<len(mat) or not 0<=newy<len(mat[0]) or visited[newx][newy]==1: continue\n",
    "\n",
    "                    queue.append(([newx, newy], step+1))\n",
    "                    visited[newx][newy] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        offset_list = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "\n",
    "        queue = deque()\n",
    "        result = [[0] * n for _ in range(m)]\n",
    "        used = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "                else:\n",
    "                    result[i][j] = float('inf')\n",
    "\n",
    "        while queue:\n",
    "            i, j = queue.popleft()\n",
    "            for offset_i, offset_j in offset_list:\n",
    "                next_i = i + offset_i\n",
    "                next_j = j + offset_j\n",
    "                if 0 <= next_i < m and 0 <= next_j < n and (next_i, next_j) not in used:\n",
    "                    used.add((next_i, next_j))\n",
    "                    queue.append((next_i, next_j))\n",
    "                    if result[next_i][next_j] > result[i][j] + 1:\n",
    "                        result[next_i][next_j] = result[i][j] + 1\n",
    "        \n",
    "        return result\n",
    "                    \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dist = [[0] * n for _ in range(m)]\n",
    "        zeroes_pos = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]\n",
    "        # 将所有的 0 添加进初始队列中\n",
    "        # q = collections.deque(zeroes_pos)\n",
    "        q = zeroes_pos\n",
    "        seen = set(zeroes_pos)\n",
    "\n",
    "        # 广度优先搜索\n",
    "        while q:\n",
    "            i, j = q.pop(0)\n",
    "            for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen:\n",
    "                    dist[ni][nj] = dist[i][j] + 1\n",
    "                    q.append((ni, nj))\n",
    "                    seen.add((ni, nj))\n",
    "        \n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        result = [[-1 for _ in range(len(mat[0]))] for _ in range(len(mat))]\n",
    "        zero_idx_lst = []\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] == 0:\n",
    "                    zero_idx_lst.append((i, j))\n",
    "        flag = 0\n",
    "        direct_lst = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        while zero_idx_lst:\n",
    "            print(zero_idx_lst)\n",
    "            tmp_lst = set()\n",
    "            for (i, j) in zero_idx_lst:\n",
    "                result[i][j] = flag\n",
    "            for (i, j) in zero_idx_lst:\n",
    "                for (gap_x, gap_y) in direct_lst:\n",
    "                    new_x, new_y = i + gap_x, j + gap_y\n",
    "                    if 0 <= new_x < len(mat) and 0 <= new_y < len(mat[0]) and result[new_x][new_y] == -1:\n",
    "                        tmp_lst.add((new_x, new_y))\n",
    "            zero_idx_lst = list(tmp_lst)[:]\n",
    "            flag += 1\n",
    "        return result\n",
    "\n",
    "                    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
